PRODUCTION SCHEDULING ALGORITHMS FOR SEMICONDUCTOR TEST OPERATIONS By REHA UZSOY A DISSERTATION PRESENTED TO THE GRADUATE SCHOOL OF THE UNIVERSITY OF FLORIDA IN PARTIAL FULFILLMENT THE REQUIREMENTS FOR THE DEGREE OF DOCTOR OF PHILOSOPHY university of Florida UNIVERSITY OF FLORIDA LIBRARIES 1990 As you set out for Ithaka hope your road is a long one, full of adventure, full of discovery. Laistrygonians, Cyclops, angry Poseidon — don't be afraid of them: you'll never find things like that on your way as long as you keep your thoughts raised high, as long as a rare excitement stirs your spirit and your body. Laistrygonians, Cyclops, wild Poseidon - you won't encounter them unless you bring them along inside your soul, unless your soul sets them up in front of you. Keep Ithaka always in your mind. Arriving there is what you're destined for. But don't hurry the journey at all. Better if it lasts for years, so you're old by the time you reach the island, wealthy with all you've gained on the way, not expecting Ithaka to make you rich. Ithaka gave you the marvelous journey. Without her you wouldn't have set out. She has nothing left to give you now. And if you find her poor, Ithaka won't have fooled you. Wise as you will have become, so full of experience, you'll have understood by then what these Ithakas mean. C.P. Cavafy ACKNOWLE DGEMENTS I would like to extend my sincere appreciation to Dr. Louis A. Martin-Vega, chairman, and Dr. Chung-Yee Lee, cochairman of my supervisory committee, for their guidance and assistance without which this work could not have been completed. Their excellent teamwork, their excellent advice on matters academic and otherwise and their willingness to sit down and reason with a stubborn Turco-Scot have set me an excellent example to follow throughout my career. Thanks are also due to Dr. D.J. Elzinga, Dr. Sencer Yeralan and Dr. Selcuk Erenguc for serving on my supervisory committee and providing me with valuable assistance and feedback as the work progressed. I should also like to thank Dr. Elzinga for helping me start my teaching career. Special thanks are due to Dr. B.D. Sivazlian for serving on my committee for a time and for his support and encouragement throughout . I would also like to acknowledge the support of Harris Semiconductor, which made it possible for me to work in a real-world environment which motivated the research in this dissertation. I would especially like to thank Mr. T. Haycock, iii Mr. P. Leonard, Mr. J. Rice and Mr. J. Hinchman for their assistance and cooperation over the last two years. It has been a pleasure to work with them. Without the support of my family and friends this work would never have been completed. To my parents, Nancy and Safak Uzsoy, goes my appreciation for their unfailing confidence, support, the excellent opportunities they have given me and the excellent example they have set me. Special thanks are due to my roommates over the last four years, who have lived a good deal of the Ph.D experience with me: David and Farah Ramcharan, Irfan Ovacik and Haldun Ay tug. Among my friends, Elias Stassinos, Serpil Unver, Clara Azcunes and Roberto Cavalieros deserve special mention. Finally, to Gerry Chestnut goes my heartfelt thanks for her support and confidence over the last difficult months, and for showing me how much growing up I still have left to do. IV TABLE OF CONTENTS ACKNOWLEDGEMENTS 1 ABSTRACT i x CHAPTERS I INTRODUCTION 1 Objectives of Dissertation 4 Outline of Remaining Sections 5 II PHYSICAL SITUATION 7 The Semiconductor Manufacturing Process 7 The Semiconductor Testing Process 10 Management Objectives in Semiconductor Testing .. 15 III LITERATURE REVIEW 18 Introduction 18 Scheduling Theory 18 Job Shop Scheduling 19 Branch and Bound Algorithms 2 4 Improvement-based branch and bound algorithms 24 Conflict-based branch and bound algorithms 2 6 Flowshop Scheduling 2 8 Heuristic Approaches 2 9 Shifting Bottleneck Approach 31 Summary 3 5 v Single and Parallel Machine Scheduling 35 Single-Machine Scheduling 36 Parallel Machine Scheduling 4 2 Batch Processing Machines 43 Research on Semiconductor Manufacturing 4 5 Summary 52 IV MODELLING APPROACH 54 Introduction 54 Modelling of Job Shop 54 Disjunctive Graph Representation 57 Approximation Methodology 61 Step 3: Determination of Critical Workcenter .. 63 Step 4: Seguencing of the Critical Workcenter . 65 Step 5: Use of Disjunctive Graph to Capture Interactions 66 Step 6: Reseguencing in the light of new Information 68 Experimentation with Overall Methodology 68 V SINGLE -MACHINE WORKCENTERS 70 Introduction 70 Description of a Single-Machine Workcenter 70 Minimizing Maximum Lateness 73 Algorithms for l/prec,SDST/Lmax 74 A branch and bound algorithm for l/prec^j ,SDST/Cmax 74 Dynamic programming algorithms for l/prec,SDST/Lmax 82 Heuristic Procedures for l/r. } ,prec f q i ,SDST/Cmax 85 vi A Neighborhood Search Algorithm 91 Minimizing the Number of Tardy Lots 95 A Heuristic Procedure for 1/prec, SDST/EU,. ... 96 Worst-Case Analysis for 1/SDST/EUj 100 Dynamic Programming Procedures for l/prec^SDST/SU, 103 Summary 105 VI BATCH PROCESSING MACHINES 108 Introduction 108 Assumptions and Notation 109 Minimizing Total Flowtime Ill Minimizing Maximum Tardiness 113 Minimizing Number of Tardy Jobs 121 Parallel Batch Machines 125 Summary 12 9 VII PROTOTYPE IMPLEMENTATION OF APPROXIMATION METHODOLOGY 131 Introduction 131 Implementation Environment 132 Implementation of Approximation Methodology 13 3 Computational Testing 13 8 Experimental Results 139 Summary and Conclusions 143 VIII SUMMARY AND FUTURE DIRECTIONS 14 5 Summary of Accomplishments 145 Single and Parallel Machines 147 Batch Processing Machines 149 VII Overall Approximation Scheme 151 REFERENCES 155 BIOGRAPHICAL SKETCH 164 Vlll Abstract of Dissertation Presented to the Graduate School of the University of Florida in Partial Fulfillment of the Requirements for the Degree of Doctor of Philosophy PRODUCTION SCHEDULING ALGORITHMS FOR SEMICONDUCTOR TEST OPERATIONS by Reha Uzsoy August 199 Chairman: Dr. Louis A. Martin-Vega Cochairman: Dr. Chung-Yee Lee Major Department: Industrial and Systems Engineering We consider a class of job shop scheduling problems motivated by semiconductor test operations but having broad applicability in other industries. Since the problem is NP- hard, we present an approximation methodology which proceeds by dividing the job shop into a number of workcenters and scheduling these sequentially. A disjunctive graph is used to capture interactions between workcenters. The performance measures to be minimized are maximum lateness and number of tardy jobs. The development of such an approximation methodology requires efficient means of scheduling the individual workcenters. in this dissertation we first consider ix workcenters consisting of a single machine. The problems of scheduling these machines are characterized by lateness- related performance measures, seguence-dependent setup times and precedence constraints, and are thus NP-hard. We provide optimal implicit enumeration algorithms and heuristics with tight error bounds for a number of these problems. Another type of workcenter considered consists of batch processing machines. A batch processing machine is one where a number of jobs are processed simultaneously as a batch. We present polynomial-time solution procedures for a number of problems of scheduling workcenters consisting of single or parallel identical batch processing machines. Finally, we demonstrate how some of the algorithms developed can be integrated into the overall approximation methodology and discuss future research. x CHAPTER I INTRODUCTION The area of scheduling deals with the problem of allocating a collection of scarce resources over time to perform a number of tasks. While first conceived in a production context, the areas of application of scheduling theory have broadened over the years to include service industries, computer system design, vehicle routing and many others. Attempts to model and guantify the scheduling process, starting around the turn of the century, have led to the development of a broad body of knowledge in this field. The deterministic scheduling problem can be defined as follows: "Given a set of n 'jobs' (tasks, events, products), that have to pass through m machines (processors) under certain restrictive assumptions, determine the schedule that optimizes some measure of performance." The development of complexity theory over the last fifteen years has provided profound insights into the nature of scheduling problems. Due to the work of researchers like 2 Lageweg, Lawler , Lenstra and Rinnooy Kan[59,60], a complete classification of deterministic scheduling problems is available. This work has shown that while many scheduling problems can be solved efficiently in polynomial time, there are a great many others for which it is unlikely that such good methods exist[42, 71] . For problems in the latter class, the researcher is forced to resort to heuristics for good solutions, or implicit enumeration methods to obtain optimal solutions. There have also, in recent years, been a number of attempts to apply techniques from other engineering fields such as artificial intelligence and control theory to solve scheduling problems. Interesting reviews of some of these research efforts may be found in Buxey[l9] and Rodammer and White [88]. While the benefits yielded by effective scheduling vary depending on the area of application, it is clear from both theory and practice that significant differences may result from the use of different schedules. This is especially the case in industries using extremely capital-intensive technologies and operating in highly competitive markets. High competition for capacity at key resources and the importance of customer satisfaction render scheduling decisions particularly critical in such enterprises. The epitome of such industries today is the semiconductor industry. 3 The miniaturization of electronic components by means of Very Large Scale Integration (VLSI) technologies has been one of the most significant technological developments of the last fifty years. Steadily improving technologies and decreasing prices have led to integrated circuits appearing in all walks of life. The computer revolution of the past two decades is a direct result of the ability to develop and fabricate these components economically. Integrated circuits can be found in almost every piece of military hardware in use today, rendering this industry extremely important from the point of view of national security. The development of complex Computer-Integrated Manufacturing (CIM) systems, essential to the maintenance of a competitive edge in today's volatile, global markets, is directly linked to the availability of the integrated components of the controllers, computers and communications equipment necessary for their implementation. Integrated circuits are also used in a wide range of industries, such as domestic appliances, cars and avionics. Thus it is safe to state that the importance of the semiconductor industry today is comparable to, if not greater than, that of the steel industry around the turn of the century. Despite the widely recognized importance of this industry, it is only in the last few years that the operational aspects of semiconductor manufacturing companies are being addressed and attempts being made to bring 4 industrial engineering and operations research techniques to bear on problems in these areas. The majority of these efforts to date, however, have focused on the extremely capital-intensive and technologically complex wafer fabrication process. The so-called 'back end' operations where the chips are packaged, tested and shipped to the customer, have remained relatively unexamined. Objectives of Dissertation The objective of the research described in this dissertation is to develop and apply production scheduling methodologies to certain job shop scheduling problems whose structure is derived from industrial settings. The primary motivation for the problems addressed in this proposal is found in testing operations within a semiconductor manufacturing facility although the classification of the problem is generic in nature. The purpose of these operations is the testing of the finished product to ensure that it meets the customer specifications. Since these operations do not add any value to the product, improvements in productivity resulting from more effective scheduling will reduce overhead, helping thus to reduce costs. An important consideration throughout this research will be the relevance of the resulting algorithms in actual real-time testing environments. 5 Outline of Remaining Sections The purpose of Chapter II is to provide the motivation for the following sections. A broad overview of the semiconductor manufacturing process is given. Test operations are placed in this perspective and described in detail. Insights into the physical situation will enable us to derive the structure of the scheduling problems addressed in this research. The purpose of Chapter III is to place the research proposed here in perspective to the existing body of knowledge in the areas of both scheduling theory and semiconductor manufacturing. The first section reviews relevant results from scheduling theory which form a basis for this work. The second section reviews applications of operations research techniques to problems in semiconductor manufacturing. Finally, the contribution of this research to the above areas is discussed in the light of these reviews. Chapter IV describes the modelling of the test facility as a job shop and the methodology with which the problem will be approached. This methodology entails decomposing the job shop into a number of workcenters and sequencing these individually, while capturing their interactions using a disjunctive graph representation of the entire facility. Chapter V presents formulations and solution approaches to the problems of sequencing workcenters consisting of a single machine under different performance measures. Chapter 6 VI examines problems related to scheduling batch processing machines. Chapter VII gives results and insights obtained from preliminary computational experience with some of the solution procedures developed in Chapter V. In Chapter VIII we present a summary of the accomplishments of this research and directions for future investigation. CHAPTER II PHYSICAL SITUATION The Semiconductor Manufacturing Process The process by which Very Large Scale Integrated (VLSI) circuits are manufactured can be divided into four basic steps: wafer fabrication, wafer probe, assembly or packaging and final testing. While the research in this dissertation is motivated by the final testing stage, we will give a brief overview of the entire process to put the testing operations in perspective and to provide the background information for some of the literature reviewed in Chapter III. Wafer fabrication is the most technologically complex and capital intensive of all four phases. It involves the processing of wafers of silicon or gallium arsenide in order to build up the layers and patterns of metal and wafer material to produce the required circuitry. The number of operations here can be well into the hundreds for a complex component such as a microprocessor. While the specific operations may vary widely depending on the product and the technology in use, the processes in wafer fabrication can be roughly grouped as follows [18]: 8 Cleaning The object of this operation is the removal of particulate matter before a layer of circuitry is produced. Oxidation, deposition, metallization In this stage a layer of material is grown or deposited on the surface of the cleaned wafer. Extensive setup times are involved, resulting in machines being dedicated to a limited number of operations. Lithography This is the most complex operation, as well as the one reguiring greatest precision. A photoresistant liguid is deposited onto the wafer and the circuitry defined using photography. The photoresist is first deposited and baked. It is then exposed to ultraviolet light through a mask which contains the pattern of the circuit. Finally the exposed wafer is developed and baked. Etching In order to define the circuits, in this step the exposed part of the material is etched away. Ion Implantation At this stage selected impurities are introduced in a controlled fashion to change the electrical properties of the exposed portion of the layer. Setups may range from minutes to hours. 9 Photoresist Strip The photoresist remaining on the wafer is removed by a process similar to etching. Inspection and Measurement The layer is inspected and measured to identify defects and guide future operations. This sequence of operations is repeated for each layer of circuitry on the wafer, in some cases up to 8 or 9 times. A detailed description of the technologies used in VLSI wafer fabrication can be found in specialized texts on this subject [90] . In the next stage, wafer probe, the individual circuits, of which there may be hundreds on one wafer, are tested electrically by means of thin probes. Circuits that fail to meet specifications are marked with an ink dot. The wafers are then cut up into the individual circuits or chips, known as dice, and the defective circuits discarded. The assembly stage is where the dice are placed in plastic or ceramic packages that protect them from the environment. This entails the placing of the chip in an appropriate package and the attachment of leads. There are many different types of packages, such as plastic or ceramic dual in-line packages, leadless chip carriers, and pin-grid arrays. Since it is possible for a given circuit to be packaged in many different ways, there is a great proliferation of product types at this stage. Once the leads 10 have been attached, the package sealed and tested for leaks, cracks and other defects, the product is sent to final test. The Semiconductor Testing Process The goal of the testing process is to ensure that customers receive a defect-free product by using automated testing equipment to interrogate each integrated circuit and determine whether or not it is operating at the required specifications. Product flows through the test area in lots. Lots vary in size from several individual chips to several thousand and are processed as a batch. Once a certain operation has been started on a lot, every chip in the lot must be processed. The actual sequence of operations a lot will go through depends on the product and on customer specification. While there is considerable variety in process flows, a general idea of product flow can be formed from Figure 2.1. Products are also classified by primary product line, as digital, analog or data acquisition. The test area is organized into cells based on this classification. The specific test system that a product can be tested on depends on the type of product only. Thus, each product can be tested only on a certain specific test system and there is no flow of work between different testing workcenters. Thus the sequence of one test workcenter will affect the sequence of another only due to the interaction 11 ■D >> CD CO £ CO O c Ll_ C i I CO c c « r- CO CD Test Insertio nvironme Screenir T3 c CO Test Insertioi Visual/ Mechanic Quality Assuranc LU -O 5s c c e nteste ventor Test sertio c i c 3 Test sertio Test sertio =3 <= c CD c c 3t o H a 3 ■O o ! a) 3 M •H 12 at non-test operations, such as brand and burn- in. The major operations taking place in the testing process are the following: Brand This operation consists of the printing of the name of the manufacturer and other information required by the customer, such as serial number, on the product package. Burn-in In this operation the circuits are subjected to a thermal stress of 125 degrees centigrade for a period of time generally not less than 9 6 hours in order to precipitate latent defects that would otherwise surface in the operating environment. This is done by loading the circuits onto boards. Each board can hold a certain number of circuits, and each circuit requires a certain specific board type. Once the circuits have been loaded onto the boards, the boards are loaded into ovens. Each oven can accommodate a limited number of boards, and certain types of circuit may require a specific oven. It is possible to load a number of different lots into the same oven. However, once the burn-in process has begun, it is undesirable to open the oven to remove or insert lots. The reason for this is that the temperature drop resulting from the opening of the door biases the test, requiring extra burn-in time for all circuits in the oven at the time the drop occurred. Thus once processing has begun, no lot in the oven, i.e., in the 13 batch being processed, can be removed until the entire process is complete. Modelling of these systems as batch processing machines will be described in Chapter VI. Quality Assurance At this step the circuits are checked visually for defects like bent leads or chipped packages, and the paperwork associated with the testing is examined to ensure that all customer specifications have been met. Testing This is the central operation of the testing process, and consists of the subjection of the components to a series of tests by computer-controlled testing equipment at various temperatures. Since this operation provides the motivation for the study of several of the scheduling problems examined in this research, we will describe this in some detail. In order for a testing operation to be able to take place, the following conditions must be met: 1) The Tester, the computer-controlled device that does the actual testing, must be available. A number of testers have separate high- and low-voltage heads, which for all practical purposes function as independent testers. 2) The Handler, a device that transfers the individual chips from the load chutes to the single set of contacts connected to the tester and then to the output bin according to the result of the test, must be available. The handlers also bring the chips to the required temperature, if high- 14 temperature (125°C) or low temperature (-55°C) testing is required in addition to room-temperature testing. The handler is restricted in the types of packages it can handle, and in some cases by temperature capabilities. 3 ) The Load Boards and Contacts , the electrical devices that form the interface between the tester and the handler, must be available. These are also package, and sometimes even product, specific. 4 ) The Test Software, to control the tester, must be downloaded from a host computer to the tester and activated. Thus, we see that the operation of setting up a tester to test a certain type of product consists of 1) Obtaining the appropriate handler, load board, contacts and bringing them to the tester or test head concerned, 2) Connecting handler, contacts and load boards to the tester, 3) Bringing the handler to the required temperature, 4) Downloading the required software. The amount of time required for these operations may be of the order of 45 minutes, which is significant compared to the processing times of the individual chips. It is also clear that the scheduling decisions can have a considerable effect on the time spent in setup. By scheduling together lots requiring the same temperature, for example, one can reduce the time spent bringing the handler to the required 15 temperature. This nature of the setup operations results in sequence-dependent setup times. It is important to note, however, that the number of distinct setup times is very- limited. The time required to change a handler, or to change temperature from room to high temperature, for example, is well known. Thus it is possible to characterize all possible setup changes with less than 10 different times. This factor will be exploited in the dynamic programming algorithms developed in Chapter V. r Management Objectives in Semiconductor Testing An example of the decision logic commonly used in practice for scheduling test equipment is illustrated by Figure 2.2. Lots that are late have priority over all others. A lot is considered to be late if its due date has passed without its being delivered to the customer. Once the late lots have been determined, the major considerations, in order of importance, are the handler and the test temperature. Once a tester is in a certain setup configuration, all lots requiring that configuration will be processed before a change is made. If a change becomes necessary, a change at the lowest possible level of the tree is preferred. In the event of a number of different requirements at a given level in the tree, the configuration that will service the largest number of lots awaiting processing is adopted. 16 CO 4-1 05 —I c < t CD _Q CO -^ 1 ■ CO n CO 1 o [X V G) O- C s- « ® CO =5 "2 (1) c CO 03 >- o - 1 - -1 >, E C 03 < CO D) O C ^- — CO — CO 3 "2 CD c CO 03 > o - 1 - -J >> E C 03 < CO i_ 2 E 3 4m* O 03 03 -1 CO >_c Q. c ■*- E |2 <g / <T> "\ CD CD C "O CD c _C CO v CJ I J r -► r A CD CD CL C < — cr CD CD _C t— (J V / CD CL E J CD CD CO oo V \ CD CD CD C "O CO c x: CD CJ X CD > CD Q_ C { — CO CD _c h- o V j f N CD Cl E _) CD a? co CO V / 01 ! 05 >, GO CO aj H a J3 a w M o MH u •H DO o c o •H 03 ■H a cu a CN 0) n ■H 17 The decision process described above provides the motivation for examining the performance measures of maximum lateness and number of tardy lots. These performance measures reflect management concerns for better customer service through on-time delivery. Explicit consideration of the setup times in the scheduling models developed addresses the concerns of shop-floor personnel for reducing time spent in setup changes. CHAPTER III LITERATURE REVIEW Introduction As indicated in Chapter I, the motivation for the problems addressed in this dissertation stems from particular job shop characteristics and parameters found in semiconductor test operations. This has led to the identification of a set of problems that are not only meaningful and original from an application perspective but also within the general context of the theory of job shop scheduling. The first part of this review will focus on the body of scheduling theory that is relevant to this research. The second section will cover research that has been carried out in industrial engineering and operations research related to modelling and analyzing semiconductor manufacturing operations in general. Scheduling Theory In this section we will present a review of the body of scheduling theory that serves as a basis for this research. We shall begin with the general job shop scheduling problem, 18 19 which is the central theme of this research. Approximate methods of solving this problem which proceed by decomposing the job shop into a number of workcenters and scheduling these iteratively are examined. The subproblems occurring in these methods lead to consideration of single and parallel machine scheduling problems. Relevant literature for these classes of problems is reviewed in the following two sections. Job Shop Scheduling For the purposes of this research we can define the job shop scheduling problem as follows. We are given a set of m non-identical workcenters, which may consist of a single machine or parallel identical machines, and n jobs to be processed. The sequence of workcenters which each job must visit is known a priori. The problem is to schedule the jobs on the workcenters so as to optimize some measure of performance. The classical job shop scheduling problem referred to by that name in the literature is a special case of the above, where each workcenter consists of a single machine that is capable of processing only one job at a time. The performance measure most commonly considered is the makespan, or time elapsed from the start to the completion of the last job. This problem is represented as J//Cmax in the notation of Lageweg et al. [59,60], and has been shown to 20 be NP-hard in the strong sense [42]. Even among NP-hard problems, it is one of the more difficult. While it is possible to solve travelling salesman problems with several hundred cities to optimality in a reasonable period of time, a 10- job 10-machine job shop scheduling problem posed by Muth and Thompson defied solution for 2 years before finally being solved by earlier and Pinson[21] in five hours of computer time. Thus, the two main avenues of attack on this problem have been implicit enumeration methods and heuristics. Before discussing these approaches, however, let us describe the representation of the J//Cmax problem as a disjunctive graph. This representation provides useful insights into the structure of the problem and has formed the basis for some of the most successful solution approaches. Disjunctive graph representation A disjunctive graph is a graph consisting of a set of nodes N, a set of conjunctive arcs A and a disjunctive arc set E. Two arcs are said to form a disjunctive pair if any path through the graph can contain at most one of them. A conjunctive arc is simply an arc that is not disjunctive. In order to represent the job shop scheduling problem as a disjunctive graph, let us introduce the concept of operations. An operation consists of the processing of a certain job at a certain machine. The problem of scheduling 21 the n jobs on the m machines can now be viewed as that of scheduling of the operations associated with the jobs on the machines. The sequence in which the jobs have to visit the machines induces precedence constraints between operations on the same job. Let N be the set of all operations, plus two dummy operations representing a source (operation 0) and a sink (operation *) respectively. Define a node i for every operation ieN. Add a conjunctive arc (i,j) if operation i has to be performed before operation j. Disjunctive pairs of arcs link operations that can be carried out at the same machine. If we let N be the set of nodes, A the set of conjunctive arcs and E the set of disjunctive arcs, we have now obtained the disjunctive graph G = (N,A,E) . Note that the set of operations N and the set of disjunctive arcs E decompose into subsets N k and E k each associated with a particular machine k. With each arc (i,j), associate a cost c^. which corresponds to the time it takes to complete operation i. To illustrate this mode of representation, consider the following example with five jobs and four machines [1] . Job Operation Machine Predecessor 111 12 4 1 2 3 1 2 4 2 3 2 5 4 4 22 Job 3 3 3 4 4 4 5 5 Operation Machine 6 1 7 4 8 3 9 1 10 3 11 2 12 3 13 2 Predecessor 6 7 9 10 12 This can be represented as the disjunctive graph in Figure 3.1. We denote by D = (N,A) the directed graph obtained by deleting all disjunctive arcs from G. For each E k , a selection S k contains exactly one member of each disjunctive arc pair. A selection is acyclic if it contains no directed cycles. Each selection S k completely defines the precedence relations of each operation to every other operation carried out on machine k. Thus an acyclic selection S k corresponds to a unique feasible sequence of the operations to be carried out on machine k. A complete selection S is the union of all selections S k over the individual machines k. When we construct a complete selection, we are able to replace the disjunctive graph G = (N,A,E) by the conjunctive graph D s = (N, A U S) . A complete selection is acyclic if D s is acyclic. Each acyclic complete selection S defines a 23 W o > •H 4-1 a a 3 a, CO n 3 M ■H fa 24 family of schedules, and every schedule belongs to exactly one such family. The makespan of a schedule that is optimal for S is equal to the length of a longest path in D s . Thus, the scheduling problem becomes that of determining an acyclic complete selection S that minimizes the length of a longest path in the directed graph D s . Branch and Bound Algorithms The disjunctive graph representation of the job shop scheduling problem has formed the basis for a number of branch and bound algorithms. These algorithms can be classified into two broad groups. The algorithms in the first class proceed by constructing an initial feasible solution and then improving it by selectively reversing disjunctive arcs. The second class of algorithms constructs a schedule until a conflict of some kind, usually violation of a capacity constraint at a machine, occurs. They then branch on each of the possible outcomes of the conflict. A similar classification of enumerative methods of solving the job shop scheduling problem is given by Lageweg et al.[61]. Improvement-based branch and bound algorithms One of the earliest algorithms in the first class was developed by Balas[8]. Let S denote the set of all complete selections and G h the conjunctive graph associated with a selection S h . Let G' be the set of all G h such that G h is 25 circuit-free. We know from the discussion above that the solution of the minimum makespan problem is equivalent to that of finding an optimal selection and minimaximal path in this disjunctive graph. The algorithm generates a sequence of circuit-free graphs G h e G' and solves a slightly modified critical path problem for each G h in the sequence. Each graph G h is obtained from a previous member of the sequence by reversing the direction of one disjunctive arc. At each stage some disjunctive arcs are fixed while some are free to be reversed, but only the candidates for reversing that lie on a critical path of the current G h need to be considered. This, however, is only true when the arc between two nodes is the shortest path between the two nodes. At each stage the shortest critical path found so far provides an upper bound, while the critical path in the partial graph containing only the fixed arcs yields a lower bound. In another paper [10], Balas provides another approach to the solution of this problem where he relates it to the concept of degree-constrained subgraph. In [9] he extends the disjunctive graph representation to handle parallel machines. In [11] he characterizes the facial structure of the polyhedra related to this problem. earlier and Pinson[21] present a branch and bound algorithm that makes use of single-machine problems to obtain bounds and various propositions which enable the size 26 of the search tree to be limited. These authors again branch by selecting a disjunctive arc and examining each of its two possible orientations. This algorithm has the distinction of having been the first to optimally solve the notorious 10- job 10-machine job shop problem posed by Muth and Thompson[21] . Confli ct-based branch and bound algorithms Charlton and Death [2 2, 23] propose an algorithm that uses the second approach. These authors start by considering only the conjunctive arcs and determining the start times for jobs on machines based on this information. They then select a machine k on which two operations i and j are processed simultaneously and branch by considering fixing the disjunctive arc (i,j) in each of its possible two directions. The lower bound at a node of the search tree is given by the critical path in the graph containing only the fixed arcs. The authors claim computational performance superior to that of Balas 1 approach[8]. Barker and McMahon[13] also propose a method that is based on branching using conflict resolution. In this approach the conflict resolution on which the branching takes place is based not on the conflict between two operations but on the conflict between an operation and several others that appear in a critical block in a tentative schedule. The method generates a tree each node of 27 which is associated with a complete schedule and a critical block of operations. At each node, a critical operation j is determined. The critical block consists of a continuous sequence of operations ending in the critical operation j . The subproblems at each of the successor nodes are obtained by fixing part of the schedule in the critical block. Lower bounds are obtained by solving single-machine subproblems using the algorithm of McMahon and Florian[76] , which is itself a branch and bound method. Florian et al.[40] also propose a branch and bound algorithm for job-shop scheduling based on the disjunctive graph representation. This approach proceeds by determining sets called cuts consisting of the first unscheduled operation of all jobs. Operations are scheduled by having all disjunctive arcs incident into the corresponding node have been fixed. The branching mechanism of the algorithm proceeds by selecting one operation from the cut to be scheduled next and fixing the disjunctive arcs accordingly. The authors prove that a graph constructed by fixing disjunctive arcs in this manner will never contain cycles and that the set of schedules enumerated in this way contains the optimal solution. The lower bound is based on the fact that each machine must perform at least one terminal operation. Hence, a lower bound for the job shop problem is obtained by sequencing the remaining jobs on each machine in order of increasing earliest start time. 28 Flowshop Scheduling The flowshop scheduling problem (F//Cmax) is a special case of the job shop problem where work flow is unidirectional. Since it has also been shown to be NP- hard[59,60] , it has also been approached using branch and bound algorithms. A number of algorithms for minimizing makespan have been developed [5,6,53,54,55,62,91]. Gupta [49], Corwin and Esogbue[29] and Uskup and Smith [92] have examined the problem of minimizing makespan in the presence of sequence-dependent setup times. However, performance measures other than makespan have not received so much attention. In [54] and [55] Heck and Roberts develop algorithms along the lines of that of Balas[8] for the measures of performance of maximum tardiness, average flow time and average tardiness. In order to minimize maximum tardiness, they introduce the concept of a critical path for maximum tardiness. This concept is then used in a manner analogous to that of Balas[8] to decide which disjunctive arcs are to be reversed. The average performance measures are handled by the same type of enumeration and branching mechanism. The difference in this case is that a sink node is associated with each job to enable the performance measures to be calculated easily. Hariri and Potts [52] have developed a branch and bound algorithm to minimize number of tardy jobs in a flowshop. However, this algorithm becomes computationally very demanding as problem size increases. 29 Heuristic Approaches The branch and bound methods described above all suffer from the common fault of implicit enumeration approaches — the exponential growth in computational effort as problem size increases. Hence a good deal of research has been devoted to developing heuristic procedures that obtain good solutions with less computational burden. We shall distinguish between two classes of heuristics: dispatching rules, that take into account only local information at the individual machines, and approximation methods, which take into account the entire job shop. There are a great many dispatching rules that have been examined in the literature. Surveys of such rules for job shop scheduling can be found in Baker[3], Conway et al.[28] and Panwalkar and Iskander [81] . Dispatching rules have the advantages of being easy to implement and explain, and will often give good results. While this approach may be sufficient for some cases, in job shops where there is high competition for capacity at key resources the extra computational effort involved in obtaining better schedules would appear to be justified. This is the motivation for the development of approximation methods, like the Shifting Bottleneck Method developed by Adams et al.[l] described in the next section. 30 An interesting application of new ideas to this problem can be found in van Laarhoven et al.[93], who apply the technique of simulated annealing to the job shop problem. These authors prove that the algorithm they present asymptotically converges to a global minimum, and finds better schedules than heuristics at the expense of higher computation times. Comparing their method with the Shifting Bottleneck procedure [ 1] , these authors found that overall the shifting bottleneck outperforms simulated annealing on the basis of a time versus quality of solution tradeoff. Matsuo et al.[75] also provide a simulated annealing procedure for the J//Cmax problem. The neighborhood structure they employ is rather more sophisticated than that of van Laarhoven et al.[93]. Their algorithm obtains solutions as good as those obtained by the partial enumeration version of the Shifting Bottleneck Procedure in comparable computation times. Another interesting class of heuristics for job shop scheduling has been developed recently based on the concept of resource pricing. An example of such an approach is given by Morton et al.[79] in the SCHED-STAR system. This system assigns a price to each machine based on the jobs waiting for it, their tardiness and inventory holding costs and the material and labor costs involved. Based on these costs a rate of return is calculated for each job and the job with the highest rate of return is scheduled next. The authors 31 report that this procedure performs better than dispatching rules over a wide range of problem instances. A number of heuristics based on approaches like neighborhood search and repeated application of Johnson's Algorithm for the two-machine case[3] have been developed for the flowshop problem. Surveys and evaluations can be found in Dannenbring[31] and Park et al.[82]. Shifting Bottleneck Approach The basic idea of the Shifting Bottleneck (SB) approach [1] is to give priority to the most critical machine. At each machine a single-machine scheduling problem is solved to optimal ity. The results are then used to rank the machines in order of criticality, the one with the worst objective function value being the most critical. The solution associated with the most critical machine is fixed as the sequence for that machine, and the procedure is repeated in the light of this information for the machines not yet scheduled. Each time a new machine is sequenced, previously scheduled machines that are amenable to improvement are reoptimized. The procedure continues in this fashion until no further improvements are possible. Having presented the broad framework, let us now present the methodology in a more formal manner. There are two important points to consider: - The nature and solution procedure for the single- 32 machine problems that are used to determine the degree of criticality of a machine as well as the sequence of the most critical - How the interactions between the individual machines are captured using the disjunctive graph representation There are a number of different ways that a machine can be classified as critical for the makespan problem. Let M be the set of machines sequenced to date, and M the entire set of machines. Denoting a selection associated with machine k as S k , we obtain a partial selection S = U k£M0 S k . Let D s be the directed graph obtained by deleting all disjunctive arcs associated with machines j , j e M \ M , and fixing the arcs in the selection S. A longest path in D s will correspond to a lower bound on the makespan. Thus, it would be mathematically justifiable to define a machine as critical with respect to a partial selection S if S k has an arc on a longest path in D s . This, however, does not allow us to rank the machines in order of criticality, but merely partitions the set of machines into two subsets, critical and non-critical. Instead, the solution to a single-machine sequencing problem is used to determine the criticality of a machine. Let us assume that we are interested in determining the degree of criticality of machine k, given that the machines j e M have already been sequenced. Create the problem P(k,M ) as follows: 33 - Replace each disjunctive arc set E p , p e M , by the corresponding selection S . - Delete all disjunctive arcs in Ej , J e M \ M Q . The release times and due dates for operations on machine k are then determined using the disjunctive graph as will be discussed shortly. The problem that results is that of seguencing a single machine to minimize maximum lateness with due dates and release times. This problem in turn is eguivalent to that of seguencing a single machine so as to minimize makespan, when each job has a release time and a certain "tail" that represents the time it must spend in the system after processing. These subproblems are solved using the algorithm of Carlier[22], which is a branch and bound procedure with good computational performance. The release times r, and due dates f 1 associated with operation i on machine k are determined from the disjunctive graph obtained from P(k,M ) above by solving a number of longest path problems. Let L(i,j) denote the longest path from node i to node j in D T , T = U keH s k . Then r, - L(0,i) where node is the source node and d. - L(0,n) - L(i,n) + d f where node n is the sink node and d,- is the processing time for operation i. The "tail" associated with operation i can then be calculated to be q, = L(0,N) - f i 34 The authors exploit the structure of the disjunctive graph to develop a longest path algorithm with a computational effort of 0(n), as opposed to the conventional algorithms that reguire 0(n 2 ) effort, where n denotes the number of nodes. The Shifting Bottleneck methodology for minimizing makespan can now be summarized as follows: 1) Identify a bottleneck machine k among the as yet unscheduled machines and sequence it optimally. 2) Reoptimize each machine h whose selection S h has an arc on a longest path in D T , keeping the other sequences fixed. If all machines are sequenced, stop. Else, go to Step 1. Computational experience with this methodology has been extremely encouraging. The authors carried out experiments on problems ranging from small ones whose optimal solution was known to larger problems with 500 operations. The approach took on the order of one or two minutes to solve the larger problems, even though a great many single-machine problems had to be solved. The authors observe that the difficulty of solving a problem increases sharply with the number of machines. However, increasing the number of operations does not seem to affect the computational effort significantly and seems to improve the quality of the solutions. A significant fact is that the classic 10 jobs/10 machines problem that resisted solution for 2 years was 35 solved optimally by the Shifting Bottleneck procedure in just over 5 minutes. When compared with priority dispatching rules, the Shifting Bottleneck Procedure outperformed them 38 out of 40 times. Adams et al.[l] have also applied the Shifting Bottleneck methodology to the nodes of a partial enumeration tree. This method most of the time yields better solutions than those obtained by applying the basic approach. Summary In the light of this review, we feel that we are able to state the following conclusions: - Approximation methods like the Shifting Bottleneck approach are the most effective solution techniques available at present for job shop scheduling problems. - Performance measures other than makespan have not been extensively examined to date. - Scheduling job shops in the presence of sequence- dependent setup times and workcenters with parallel identical machines and batch machines has not been examined extensively. Single and Parallel Machine Scheduling The effectiveness of approximation methods like the SB approach described in the previous subsection hinges on the ability to efficiently schedule the individual workcenters. 36 These workcenters may consist of a single machine, or a number of parallel identical machines. In this subsection we will review results on single and parallel machine scheduling that will assist us in developing solution procedures for the workcenter subproblems. Single-Machine Scheduling Research on the sequencing of a number of jobs through a single processor dates back to the 1950s. In this section we shall only review results relevant to this research. Reviews of the basic results in this area can be found in Baker [3], Conway et al.[28] and French [41]. Detailed complexity classifications of these problems are given by Lageweg et al. [59,60]. The nature of the facility motivating this study and the management objectives involved lead us to examine single-machine scheduling problems with performance measures of maximum lateness and number of tardy jobs. The problems are characterized by the presence of release times, due dates, precedence constraints and sequence-dependent setup times. In order to represent these problems in a concise manner we shall extend the notation of Lageweg et al. [59,60] to include sequence-dependent setup times (SDST) . Thus, for example, the problem of minimizing Lmax on a single machine with precedence constraints and sequence-dependent setup times will be represented as l/prec,SDST/Lmax. 37 The problem of minimizing Lmax on a single processor without setup times has been extensively examined. The cases with simultaneous release times (1//Lmax and 1/prec/Lmax) are easy to solve using the Earliest Due Date rule and Lawler's Algorithm respectively [3 , 64] . However, the presence of non-simultaneous release times renders the problem 1/rj/Lmax NP-hard in the strong sense [60]. Thus we see that our problem, l/r j# prec, SDST/Lmax, is NP-hard in the strong sense even without the seguence-dependent setup times. Furthermore, we note that the special case of 1/SDST/Lmax with common due dates is eguivalent to 1/SDST/Cmax, which is well known to be eguivalent in turn to the Travelling Salesman Problem (TSP) [3]. The l/rj/Lmax problem has been examined by a number of researchers. It has been shown that this problem is eguivalent to the problem of minimizing makespan (Cmax) on a single machine in the presence of delivery times q. = K - d-, where K > max^d,} [71]. The optimal seguences for these two problems are identical, and their optimal values differ by the constant K. We shall denote this problem by l/r^qj/Cmax. Branch and bound algorithms for this problem have been developed by Baker and Su[7], McMahon and Florian[76] and Carlier[20] . The latter two approaches are closely related and both have been integrated into larger branch and bound schemes for solving the general job shop problem[13,21] . 38 Baker and Su[7] develop an enumeration scheme that enumerates all active schedules. Active schedules are those schedules in which no job can be started earlier without delaying the start of another. Let S be the set of all jobs. Then at time t the set Q of jobs eligible for scheduling next is Q = {jes|rj < min{max{t,r k }+p k } |keS} This ensures that only active schedules are generated, since if r } > max{t,r k } + p k for some job k, then k can precede j without delaying the completion of j . The bounding rule employed is based on the fact that the value of an optimal schedule will not increase if job splitting is allowed. A lower bound for all completions of a partial schedule is obtained by seguencing the remaining jobs in EDD order allowing job splitting. This algorithm can easily be extended to the problem with precedence constraints by defining the set Q to be the set of jobs whose predecessors have been scheduled that satisfy the condition specified above. A more sophisticated algorithm is given by McMahon and Florian[76]. This approach uses a heuristic to construct a good initial solution and then generates an enumeration tree of improved solutions. The heuristic selects the job available at time t that has the earliest due date, breaking ties by choosing the job with longest processing time. The resulting schedule consists of a number of blocks, which are 39 periods of continuous utilization of the machine. The authors define the critical job to be the job that realizes the value of Lmax in a given schedule. Branching rules and lower bounds are obtained by scheduling other jobs last in the block instead of the critical job. The algorithm of Carlier[20] is closely related to that of McMahon and Florian[76] and also makes use of the same heuristic. This author proves that if L is the makespan of the schedule obtained using this heuristic, then there exists a critical job c and a critical set J such that min {r,.} + s p. + min {q,.} > L - p c ieJ ieJ ieJ and that in an optimal schedule job c will be processed either before or after all the jobs in J. This latter observation forms the basis of the branching rule employed. Lower bounds are obtained by applying the heuristic but also allowing preemption. This algorithm has excellent computational performance, and has been integrated into algorithms for the job shop problem developed by Carlier and Pinson[21] and Adams et al.[l]. Potts[85], Carlier[20] and Hall and Shmoys[51] present heuristics for the l/rj , qj/Cmax problem and analyze their worst-case behavior. Most of these heuristics are based on the Extended Jackson's Rule, which can be stated as follows: Whenever the machine is free and there are one or more available operations, sequence next the operation with largest value of q { . The best heuristic developed so far 40 appears to be that of Potts quoted by Hall and Shmoys[51], which has a worst-case error of one-third. The performance measure of number of tardy jobs (SU-) is considerably more difficult to optimize than Lmax. The problem 1//SU,- can be solved in polynomial time using Moore's Algorithm[3] . Lawler[65] extends this approach to the V/SWjU. problem where w- < Wj implies p. > p jf where w- is a nonnegative penalty for the job j being tardy. However, the general l//T,w.\J. problem and the 1/prec/SU,. problem are both NP-hard[59,60,72] . Lawler and Moore [66] give a pseudopolynomial dynamic programming algorithm for the former problem, and Villarreal and Bulfin[96] and Potts and Van Wassenhove[86] provide branch and bound algorithms. The algorithm of Potts and Van Wassenhove uses problem reductions derived from the knapsack problem and dominance relations to reduce the size of the search tree. Lower bounds are derived from the dynamic programming algorithm of Lawler and Moore [66] and a linear programming relaxation of the integer programming formulation of the problem. The problem with arbitrary release times and due dates, 1/rj/EUj , is also NP-hard in the strong sense [59, 60] . Kise et al.[58] give a polynomial time algorithm to solve the case with agreeable release times and due dates, i.e., r- > r- implies d,- > d, . It is well known that the problem of minimizing makespan on a single machine with sequence-dependent setup 41 times (1/SDST/Cmax) is equivalent to the travelling salesman problem (TSP) , which is NP-complete[3] . Picard and Queyranne[84] relate the problems of minimizing weighted lateness, number of late jobs and the sum of weighted tardiness and flow-time costs to the time-dependent TSP. In this generalization of the TSP the cost of each transition depends not only on the locations between which it takes place but also on the position of the transition in the sequence defining the tour. These authors use relaxations of integer programming formulations to obtain bounds which they use in a branch and bound algorithm. Barnes and Vanston[14] address the problem of minimizing the sum of linear delay costs and sequence-dependent setup costs, where the delay is defined as the time elapsing until the job starts being processed. They examine a number of branch and bound algorithms and develop a hybrid dynamic programming/branch and bound approach. Driscoll and Emmons [39] present a dynamic programming formulation of the problem and demonstrate some monotonicity properties of the functions employed. A number of authors, such as Lockett and Muhlemann[73] , White and Wilson[98] and Irani et al.[57] have also developed heuristics. These heuristics generally entail some analysis of the setup operations and the approximate solution of the resulting TSP. 42 The problems of minimizing Lmax or SU,- with sequence-dependent setup times (1/SDST/Lmax, 1/SDST/SU,-) do not seem to have been extensively examined. Monma and Potts [78] present a dynamic programming algorithm and optimal ity properties for the case of batch setups, where setups between jobs from the same batch are zero. Parallel Machine Scheduling Lageweg et al. [59,60] give a detailed complexity classification of results in parallel machine scheduling without preemption. From this classification it appears that only problems with unit processing times can be solved in polynomial time. The problems P2/r,, d-, p-l/L^, P/r., d-, Pj^l/SWjTj. and P/rj, dj, Pj-l/SWjUj are among these [63]. The other problems in this area are either open or NP-hard. Considerable effort has been devoted to the development and analysis of heuristics for these problems [26, 37] . The problem of scheduling parallel machines in the presence of sequence-dependent setup times has also been addressed by a number of researchers. Geoff rion and Graves [43] examine the problem of scheduling parallel production lines in the presence of changeover costs and formulate it as a quadratic assignment problem. Wittrock[99] presents a heuristic for minimizing total completion time on a set of parallel identical machines where there are two types of setups: "family" setups, which are more time- 43 consuming and are incurred when the product being run changes drastically, and product setups due to changes from one product to another in the same family. Computational experience is reported and a lower bound for the optimal solution derived. Dietrich [38] examines the problem of determining schedules that are efficient with respect to both makespan and flow time for the case of parallel unrelated machines with sequence-dependent setups. An integer programming formulation is presented and a heuristic algorithm developed. Parker et al.[83] use a vehicle-routing algorithm to solve the problem of minimizing total setup costs on parallel processors. Batch Processing Machines A batch processor is defined to be a machine where a number of jobs can be processed simultaneously as a batch. The processing time of a batch is equal to the longest processing time among all jobs in the batch. Once processing is begun on a batch, no job can be removed from the machine until the processing of the batch is complete. These problems are motivated by burn-in operations in the semiconductor industry, where lots of chips are placed in ovens and subjected to thermal stresses for an expended period of time in order to bring out latent defects leading to infant mortality before the product goes to the customer. The scheduling of batch processors does not seem to have 44 been extensively examined in the deterministic scheduling literature to date. Ikura and Gimple[56] provide an 0(n 2 ) algorithm to determine whether a feasible schedule (i.e., one where all jobs are completed by their due date) exists for the case where release times and due dates are agreeable and all jobs have the same processing time. In the event of a feasible schedule existing, their algorithm finds the one with minimum finishing time. Bartholdi[15] examines the problem of minimizing makespan on a single batch processor. He shows that successively grouping the B longest jobs into a batch will minimize makespan for the case where all jobs are available simultaneously. Ahmadi et al.[2] examine the problems of minimizing mean flow time and makespan in flowshops consisting of batch and unit-capacity machines, assuming that all jobs reguire the same processing time on the batch machine. They provide polynomial-time algorithms for a number of cases and provide NP-completeness proofs and heuristics for others. Related problems seem to have been more extensively examined from a stochastic perspective. Neuts[80] considers a case where customers are served in groups. Service can only start if a certain number of customers are waiting, and the number of customers which can be served together is limited. He examines system characteristics such as the output process, gueue length and number of customers served over a long period of time. Medhi[77] examines the 45 distribution of waiting times in this system when service times are exponential. Deb and Serfozo[36] use dynamic programming to minimize expected total or average costs. Concluding this subsection, it emerges that the problems in the areas of single, parallel and batch machine scheduling of the types examined in this research have not been examined extensively in the literature and a great many of them are NP-hard. Research on Semiconductor Manufacturing Despite the ever-increasing role played by the semiconductor industry in worldwide technological development it is only recently that semiconductor manufacturing systems have attracted the attention of industrial engineering and management science researchers. One of the earliest articles available in the published literature is that of Burman et al.[l8] which discusses methods of using various operations research tools to enhance productivity in wafer fabs. They compare the usefulness of simulation, deterministic capacity models and queueing models. Simulation models can be developed to model an entire production operation with a view to answering many potential questions, or as smaller models to address specific issues. However they point out that considerable effort is needed to develop the model and to analyze the output. Deterministic capacity models are used 46 for capacity estimation purposes, are easy to develop and quick to run but limited in the range of questions they can address. Queueing models can be developed that can be used to examine a broader set of issues than the deterministic capacity models, but the mathematical assumptions they make tend to render them inaccurate representations of the physical system. The authors then proceed to give an example for the application of each technique in a wafer fab environment. Considerable effort has gone into the development of simulation models for wafer fabs and their use to analyze the effects of different control strategies. Dayhoff and Atherton [32,33,34,35] have developed such a model and used it to analyze the performance of wafer fabs under different conditions. Their approach is based on modelling a fab as a special type of queueing network. Similar approaches, namely the modelling of the wafer fab as a network of queues and the subsequent use of a simulation model, are followed by Wein[97], Glassey and Resende[44 , 45] and Lozinski and Glassey[74]. Wein[97] evaluates the effect of scheduling on the performance of wafer fabs, taking cycle time as the measure of interest. He examines two different types of control strategy: regulation of input, where the number of lots started into the fab is controlled, and sequencing of lots at the individual stations. He observes that input regulation yields larger improvements than sequencing at the 47 individual stations, and that the effects of sequencing rules depend heavily on the number and location of the bottleneck stations and the specific input regulation mechanism involved. Glassey and Resende[44, 45] point out that due to the extensive use of Computer-Integrated Manufacturing (CIM) systems such as the COMETS system [27] dispatching decisions at the individual stations and lot release decisions governing the release of work to the fab can be made based on more global information. Similarly to Wein[97], they examine the effects of input regulation mechanisms, assuming they have a single bottleneck workstation in a fab with a single product and constant demand rates. They develop a rule for input regulation which attempts to release work into the fab so that it will arrive at the bottleneck station just in time to stop it from starving. The authors compare this strategy with a number of others and report favorably on its performance, which is measured based on a tradeoff between cycle time and throughput. Lozinski and Glassey [74] discuss implementation issues. Leachman et al.[68] further develop this approach by removing the need for a priori bottleneck determination. Spence and Welter [89] use a simulation model to examine the performance of a photolithography workcell based on a throughput-cycle time tradeoff. 48 Chen et al.[24] develop a queueing network model of a research and development wafer fab operation. A network in which a number of different types of customer, corresponding to different lot types, are present is presented. The model is of a mixed nature, that is, open for certain classes of customers and closed for others. After defining parameters such as expected number of visits to each station and station service rates, an iterative procedure is employed to arrive at throughput rates for the entire network and other quantities of interest such as average throughput time per customer at each station. The results obtained from the model are compared with actual observed data and found to be in close agreement. Bitran and Tirupati[16, 17] describe a scheduling system for a facility manufacturing epitaxial wafers. They model this facility as a single-stage parallel-machine system, and propose a number of heuristics with a view to optimizing two criteria, makespan and total tardiness. They also examine product mix and the associated problem of assigning product families to reactors so as to achieve a more homogeneous product mix. This is formulated as a convex program. They recommend various different heuristics for different cases, and observe that when the jobs are preprocessed by assigning product families to reactors a priori, simpler heuristics give results comparable to the more complex procedures they develop. 49 As can be seen from the above review, the majority of the approaches to scheduling of semiconductor manufacturing facilities are of the nature of input regulation mechanisms and dispatching rules at the individual stations. A significant exception is the work of Bartholdi et al.[15] which is related to the work in this dissertation. The most important part of these authors 1 work is their application and extension of the Shifting Bottleneck (SB) approach of Adams et al.[l] to wafer fabrication operations. These authors model the wafer fab using the SB approach and extend the basic model in various ways to include parallel identical machines and batch processing machines. To model parallel identical machines, they start from the observation that a sequence for a single machine k corresponds to a path connecting all nodes in the associated selection S k . A schedule for a workcenter with m parallel identical machines will then correspond to m disjoint paths, each one corresponding to the sequence for one of the m machines. Each node corresponding to an operation has to be visited by one and only one path. Batch processing machines are represented using stars. An n-star is a graph with n-1 arcs containing a node c, called the center, which is adjacent to all other nodes, called satellites. If a batch can be processed at a workcenter, this can be represented by a star with a center corresponding to the operation with the longest processing time. The costs of the arcs leaving the 50 satellites are set to 0, and the costs of the arcs leaving the center are set to the longest processing time in the batch. In the case of several batches being available, there will be as many stars as batches. This assumes, however, that the assignment of operations to batches is already known . Leachman[67] gives a corporate-level production planning model for the semiconductor industry. He divides the manufacturing process into the stages of fab, probe, assembly and test, linked by inventories. The model may include multiple facilities, and treats entire production processes in each plant as integral entities. Products undergoing the same process at each stage are aggregated into families. Computerized routines create the input files of an aggregate planning model and then generate the linear programming formulation. The solution to this linear program yields a production plan at the process level of detail, which is then validated by management. If it is invalid, due to some resource being overutilized for instance, the input data are revised and the process repeated until an acceptable plan is generated. Once an aggregate plan has thus been obtained, it is disaggregated by solving a number of linear programs to divide the volume of production planned for each product family over the individual products. This model has been used by a number of manufacturers in the industry. 51 A number of commercial software systems for the planning and control of semiconductor manufacturing operations have been developed. One such system widely used in industry is COMETS [27], marketed by Consilium, Inc. and used by a number of leading companies. This system is composed of a number of different modules, and is designed as an integrated plant management system, with all the different groups involved in the manufacturing process being supported by the same database. The main modules of interest to this study are the Work-in-Process (WIP) tracking module, the Activity Planner/Dispatch (AP/D) module and the Short- Interval Scheduling (SIS) module. Other modules such as engineering data collection, factory communications and on- line specifications are also available. The Short-Interval Scheduling (SIS) module of COMETS gives the user real-time scheduling capabilities. The process is modelled using the concept of dispatch stations, which are essentially points in the process where inventory accumulates and a scheduling decision is reguired. SIS enables the user to develop his own dispatching rules. This is done by defining a set of priority classes, with a strict hierarchy, and then using rules to define the conditions under which a lot may be a member of a class. Lots at the dispatch station are prioritized according to the status of the system at the moment the reguest for the dispatch list was made, and the operator selects the lot with the highest 52 priority for processing. The module makes information like machine status (up/down, setup) at the dispatch station itself or a subsequent station, time spent by a lot at the station and setups required by lots awaiting processing available to the user. Detailed information on this software module can be found in Consilium[27] . Thus, the scheduling technology present in this system is the classical dispatching rule, using mostly local information in the immediate environs of the dispatch station and not using global information at all. Summary In this chapter we have reviewed the current body of knowledge in the areas of scheduling theory and its applications in semiconductor manufacturing. We shall now examine the contributions of the research in this dissertation to these areas. The problems of scheduling the job shop to minimize maximum lateness and number of late jobs are NP-hard and have not been extensively studied. The excellent computational performance of the SB methodology for minimizing makespan would suggest that similar approximation methods will rapidly yield good solutions for these problems. The development of such methods contributes significantly to the area of job shop scheduling. The extension of the job shop model to include multiple-machine 53 workcenters and batch processing machines also extends modelling capabilities in this area. The single, parallel and batch processing machine problems that constitute the subproblems in an approximation approach are also of considerable interest and have not been examined extensively in the literature. In Chapter V exact and heuristic solution procedures for the problems of minimizing maximum lateness and number of tardy jobs are developed. The worst-case analysis of the heuristics developed is the first such analysis known to the author for problems of this type. In Chapter VI the problem of scheduling batch processing machines for a number of different performance measures is examined. Optimal solution procedures and heuristics are presented, together with a complexity classification of these problems. The problem of scheduling in the semiconductor industry seems to have been addressed mainly through dispatching rules. The ultimate goal of this research is the development of algorithms capable of being incorporated into a decision support tool to assist shop-floor personnel in real-time decision-making. This would constitute a significant improvement over available commercial scheduling systems, which are based solely on dispatching rules. The consideration of the status of the entire job shop should yield considerably better schedules, especially for bottleneck resources. CHAPTER IV MODELLING APPROACH Introduction In this chapter we shall formulate the problem of scheduling a semiconductor test facility as a job shop scheduling problem. We shall then present an approximate solution methodology for this problem similar to the Shifting Bottleneck (SB) methodology of Adams et al. [1] for the J//Cmax problem described in the previous chapter. The basic SB methodology is extended in a number of ways to be able to address the type of job shop under study. Chapters V and VI develop algorithms necessary to solve the local problems in the approximation approach, and a prototype implementation of the approximation scheme is described in Chapter VII. Modelling of Job Shop In a semiconductor testing facility, product moves through the area in lots, which vary in size from a few individual chips to several thousand. Once processing of a lot has begun, it cannot be interrupted until the whole lot has been completed. Processing takes place at a number of workcenters, generally consisting of one or more identical 54 55 machines. The machines may be testers, branders or burn-in ovens, to name a few. These machines differ considerably in scheduling characteristics. For example, testers have sequence-dependent setup times, while branders do not. Test systems and branders can process only one lot at a time, while burn-in ovens can process a number of lots together as a batch. Hence a natural way to model a semiconductor test facility as a job shop scheduling problem is to model each lot of chips as a job, and each group of similar machines scheduled as a unit as a workcenter. Note that this is a somewhat more general problem than the classical job shop scheduling problem discussed in Chapter III. The common assumptions in this problem are that each machine is visited by each job only once, that each machine can process only one job at a time and that setup times are not sequence-dependent. In the semiconductor test facility that provided the motivation for this study, however, there are several differences from this model: - The presence of different types of workcenters, some consisting of multiple identical machines, some of a single machine and some of one or more batch processing machines, where a number of jobs are processed together as a batch. - The presence of sequence-dependent setup times at some workcenters . - The performance measures being related to lateness 56 instead of makespan. - The possibility that a given job may return to a certain workcenter more than once (reentrant work flows) . For example, if a lot of chips has to be tested at three different temperatures, all three operations are carried out at the same test workcenter. This also results in the presence of precedence constraints between operations at a given workcenter, a complication not present in the classical J//Cmax problem. Recall from Chapter III that the disjunctive graph representation of the job shop scheduling problem has formed the basis for many solution approaches. From the point of view of this research, the most important application is the use made of it in the SB methodology to capture interactions between different workcenters as the methodology proceeds and a complete job shop schedule is built up. We shall now give the disjunctive graph representation of the job shop defined by a semiconductor test facility and describe how it is used to capture interactions between individual workcenters. Throughout the rest of this chapter, we will make the following assumptions: - All handlers, load boards , contacts and operators are freely available at all times -Operations on the same lot have a strict precedence relation which is known a priori. Once processing on a lot has started, the entire lot has to be completed. 57 - All the process times and sequence-dependent setup times are available and deterministic. Disjunctive Graph Representation In order to construct the disjunctive graph representation of the job shop, let us first consider the case of a workcenter consisting of a single machine. The following notation will be used: ij = operation i of lot j P,-j = processing time for operation i of lot j s ij,ki = setu P time required for change from operation i of lot j to operation k of lot 1 on the workcenter Let us now construct the disjunctive graph representation of the workcenter as follows. Assume there are N operations to be processed at the workcenter. Add a source node 0, and associate a node ij with each operation j to be carried out on lot i at the workcenter. With each lot i to be processed at the workcenter, associate a sink node i* that represents the completion of that lot. This is similar to the approach used by Heck and Roberts [55] for average tardiness minimization in flowshops. Define the arc set as follows: -Associate a conjunctive arc (ij,kl) between pairs of operations ij and kl where ij must precede kl at the workcenter. Each of these arcs represents a precedence constraint between the two operations corresponding to the nodes at each end. Add a conjunctive arc (0,ij) from the 58 source node to all nodes representing operations ij having no fixed predecessor, and another conjunctive arc (ij,j*) from all nodes ij representing the final operation ij on lot j to the sink node. -Associate a pair of disjunctive arcs between all pairs of nodes (ij,kl) that correspond to operations that can be carried out at the workcenter and have no precedence relation. -With each arc, conjunctive or disjunctive, associate a cost Cjj. kl defined as c U,ki = Pij + s ij,ki Assume p 0j = o for all j . The sequence-dependent setup times are thus taken into account. All process and setup times associated with the sink nodes i* are assumed to be zero. An example of a workcenter with three lots is shown in Fig. 4.1. Arc costs are omitted for the sake of clarity. The first lot has two operations, represented by nodes 11 and 21, while two other lots have one operation each. Notice that each path from source to sink consisting of only conjunctive arcs corresponds to a lot. Operation 11 has to be carried out before operation 21, hence the conjunctive arc between nodes 11 and 21. The possible sequences of operations for this workcenter are described by the pairs of disjunctive arcs. Each sequence for the workcenter corresponds to a selection of exactly one of each disjunctive pair. The sequence of operations 11-21-12- 13, for example, is represented by the graph in Fig. 4. 2. 59 ® © M 0) i-i (3 0) a M U o at M O ■+a Jti 0, ns N O > •H -u o 3 | u 50 ■H 60 u a) u G 0) a M U o w c 3 -n cu .c u Cfl P o ■H 4-1 ct! 4J c en cu a. £ CO CM <r 0) t-i 3 Si) T-I 61 In order to represent the entire job shop as a disjunctive graph, we represent each workcenter in the manner described above. However we no longer define a source and sink node for each workcenter. Instead the nodes that would be linked to the source at each workcenter are now linked to nodes corresponding to operations on that lot at preceding workcenters. We create a source node for the entire facility, to which all nodes corresponding to operations with no predecessors are linked, and again associate a sink node i* with the completion of the final operation on each lot i. An example for a job shop with two workcenters is shown in Fig. 4. 3. Operations 11,21,12 and 13 take place at the first workcenter, while 31, 22 and 23 take place at the second. Lots must be processed at the first workcenter before they can be processed at the second. Nodes 1*, 2* and 3* denote the completion of the lots. Approximation Methodology Now that we have formulated the problem of scheduling a semiconductor test facility as a job shop scheduling problem and have shown how it can be represented using a disjunctive graph, we are ready to present an approximation methodology for its solution similar to the SB methodology of Adams et al.[l]. The approach may be outlined as follows: 1) Divide the job shop into a number of workcenters numbered 1, . . . ,m that have to be scheduled. Let M be the set 62 o js w ■a o o P. ca O a) > •H 4J U S 3 Q p-l ft u p faO 63 of workcenters, and M the set of all workcenters that have been sequenced. Initially, M = <p. 2) Represent the job shop using a disjunctive graph. 3) From among the non-sequenced workcenters k e M \M , determine the most critical workcenter j . 4) Sequence the critical workcenter j. Fix the selection of disjunctive arcs Sj corresponding to this sequence. Set M = M U {j}. 5) Use the disjunctive graph representation to capture the interactions between the workcenters already scheduled and those not yet scheduled. 6) Resequence those workcenters that have already been sequenced using the new information obtained in Step 5. If VL = M, stop. Else, go to Step 3. The main body of the methodology is contained in Steps 3 through 6. We shall now discuss each of these steps individually. Step 3; Determ ination of Critical Workcenter The objective of this phase is to determine which workcenter is most critical, in the sense that a poor schedule on that workcenter will result with high probability in a poor overall schedule for the job shop. For this stage, Adams et al.[l] use the optimal solution to a relaxed problem which ignores machine interference between machines not yet sequenced. Since all of their subproblems are of the same type 64 and are solved to optimal ity, this is a good indicator since all machines are compared equally. In the case of the job shops under study here, this issue becomes more complicated. While extremely fast branch and bound algorithms are available to solve subproblems for workcenters without setup times, such methods are not yet available for the case where sequence-dependent setups are present. This would seem to force us to use heuristics to obtain solutions to the relaxed problems for this type of workcenter, thus losing the common denominator of optimality present in the case of Adams et al.[l]. One possibility is to try and ensure equitable comparisons between the different types of problems by using heuristics with comparable performance to evaluate each different type of workcenter problem. In this case we would define performance in terms of average or worst-case performance. The prototype implementation described in Chapter VII uses this approach. An interesting point is that although in their methodology Adams et al.[l] use the algorithm of Carlier[20] both to make criticality decisions and to sequence the critical workcenter, there is no apparent need to do so in the case of the more general shops under consideration in this research. In the case of Adams et al.[l] the use of the same algorithm for both purposes is extremely logical, since all subproblems are of the same type and the optimal sequence of 65 the critical machine is available at the end of the first stage anyway. However, in view of the intrinsically more difficult subproblems considered in this study, it might make sense to use a fast heuristic to make criticality decisions and a more computationally intensive algorithm to sequence the critical workcenter as well as possible. This makes even more sense when we note that the problems relating to criticality decisions have to be solved for each unscheduled machine, while the problem of sequencing the critical machine need only be solved for that one machine at each iteration of the general methodology. Step 4; Sequenc ing of the critical workcenter This phase consists of finding a good, preferably optimal sequence for the critical workcenter, fixing it and modifying the constraints such as finish times and release times on other machines according to the results obtained. An algorithm used at this stage should ideally be fast from a computational point of view and generate solutions whose deviation from the optimal could be bounded within a reasonable interval. Extremely efficient branch and bound algorithms are available in the literature for the cases without sequence-dependent setup times. In the next chapter we present optimal and heuristic algorithms for single-machine workcenters with sequence-dependent setup times. How some of these algorithms can be incorporated into the approximation 66 methodology is illustrated in the prototype implementation in Chapter VII. Step 5: Use of Disjunctive Graph to Capture Interactions Note that when a certain subset of the workcenters have been sequenced, certain constraints are imposed on the sequencing problems for the remaining workcenters. Jobs will become available for processing at certain times (release times) depending on how the previous workcenter is scheduled. It is also important to have estimates of the time by which an operation must be completed on a particular workcenter (operation due dates) in order to allow the lot it is performed upon to complete on time. These operation due dates, in turn, form the input to the algorithms used to determine and schedule the critical workcenter. If we fix the disjunctive arcs associated with the sequences of workcenters already sequenced, we can estimate the release times and operation due dates for operations by performing a number of longest path calculations in the resulting directed graph, in a manner analogous to calculating early start and latest finish times in a CPM problem[3]. If we denote by L(ij,kl) the length of a longest path from ij to kl in the directed graph described above, the release time, i.e., the earliest start time, of operation ij is given by r fJ = L(o,ij) - s kljJJ where kl is the operation preceding ij on the longest path 67 and the operation due date d.. by d U " d i " L(ij,i*) + P,-j Both these expressions use the longest path operator L(ij,ik) to estimate the time that will elapse between the start of operation ij and the completion of operation ik. Note that in most cases this will underestimate the actual time needed, since it will ignore machine interference effects at the machines not yet scheduled. A similar approach for the estimation of operation due dates from job due dates has been used by Vepsalainen and Morton [ 94 , 95] and Baker [4]. An extensive survey of the literature on due date estimation can be found in Cheng and Gupta [25]. Thus the graph representation is used to capture interactions between the different workcenters. Each time a workcenter is sequenced, the due dates and release times of operations on other workcenters are updated in order to include the constraints imposed on the entire system by the sequencing of that machine. It is clear from the above discussion that the solution of the longest path problems required to set up the local problems at each iteration will form a major part of the computational burden of the approximation methodology. Adams et al.[l] have developed a longest path algorithm that exploits problem structure and has 0(n) complexity as opposed to the 0(n ) complexity of conventional longest path algorithms. This algorithm must be extended to the case where 68 parallel identical machines and batch processing machines are present. However, when each workcenter consists of a single machine it results in substantial savings in computation time. Step 6: Resecru encina in the light of new information . This step consists of resequencing the workcenters that have already been sequenced in the light of the constraints imposed on them by fixing the schedule of the latest scheduled machine. The main point here is that it may not be necessary to resequence all machines already sequenced. Some machines may not interact at all with the newly scheduled machine, and thus the sequence on this machine will not affect them at all, while others may be affected only insignificantly. What is needed here is some way of determining what machines are the most important to resequence, taking into account the structure of the job shop and other relevant information. Heck's extension of the concept of a critical path to lateness [54] may form the basis of an approach to this. Experimentation with Overall Methodology The development of an efficient methodology based on the Shifting Bottleneck concept for the types of job shops studied here clearly requires a good deal of empirical work. The methodology itself will consist of a combination of heuristics and optimization algorithms to make the criticality decisions and sequence the critical workcenters. Other heuristics may 69 be used to determine which workcenters should be resequenced at the end of each iteration. The sensitivity of the overall procedure to the various procedures used for each of these purposes needs to be extensively investigated. The empirical analysis of such a complex approximation procedure for a large combinatorial optimization problem poses interesting difficulties. First of all, one issue is the determination of how good are the results of the approximation scheme. Comparison of the results of the approximation procedure and dispatching rules, which currently constitute the state of the art in most industry environments, is one approach. This would allow a statistical comparison of the procedures to be made [47]. Estimation of how close to the optimum results are, however, is more difficult due to the fact that obtaining optimal solutions to realistic problems is prohibitively time-consuming. For this purpose, use of statistical techniques to estimate optimal values offers one avenue of approach. Such techniques have been developed and documented by Dannenbring[30] and Golden and Alt [46]. The overall goal is configure a specific methodology for the type of job shop under consideration, specifying what algorithms to use at each step for each type of subproblem, in order to arrive at a robust way of obtaining good solutions. CHAPTER V SINGLE -MACHINE WORKCENTERS Introduction In the previous chapter the main methodology with which the problem of sequencing the job shop under study would be attacked was outlined. This methodology requires repeated solution of subproblems related to the sequencing of individual workcenters. In this chapter, problems motivated by the modelling of workcenters consisting of a single machine will be formulated as scheduling problems and methods for solution presented. Description of a Single-Machine Workcenter These problems were motivated by the need to schedule workcenters consisting of a single tester. A number of lots, some of which may require more than one operation with different setups, need to be processed at the workcenter. If a lot requires more than one operation, there are strict precedence constraints between them defining the order in which they have to be performed. Note that a special precedence structure results since there are no precedence 70 71 relations between operations on different lots. Thus, the problem becomes that of sequencing a number of "strings" of operations which must be processed in the order suggested by the precedence constraints but not necessarily in immediate succession. An example of the precedence graph for a single- workcenter problem with three different lots is shown in Figure 5.1. All operations on the same lot have the same due date. The measures of performance we wish to optimize are functions of the completion times and due dates of the lots, not of the individual operations. The performance measures of maximum lateness of a lot and number of tardy lots will be examined in this research. Due to the nature of the production technology, the sequence-dependent nature of the setups is explicitly considered. Let us define the following notation for the single- workcenter problem: n = number of operations to be scheduled m = number of lots to be scheduled N = set of operations to be performed at the workcenter ij = operation i on lot j P,-j ■ processing time of operation i of lot j on the workcenter d.- } = due date of operation i of lot j 72 CD M 3 u o 3 u ■u <u y c 01 -a 0) o 0) H m M M •H 73 s ij,ki = set up time necessary to change from operation i of lot j to operation k of lot 1 on the workcenter rj » the time the lot j becomes available at the workcenter, i.e., the release time of lot j In order to integrate the subproblems into the main approach, it is necessary to include release times r,. These times represent the time the lot arrives at the workcenter from previous processing steps. However, in order to gain insight, we shall first relax the release times. In a later section we shall examine heuristics for the case with non- simultaneous release times. Minimizing Maximum Lateness The first problem we shall examine is that of minimizing maximum lateness (Lmax) of a lot. This can be stated as follows: "Minimize the maximum lateness of a lot in the presence of precedence constraints and sequence-dependent setup times. " Extending the classification of Lageweg et al. [59,60], this problem will be written as l/prec,SDST/Lmax, where SDST denotes the presence of sequence-dependent setup times. Recall from Chapter III that this problem is NP-hard. Thus the approaches left open to us are the development of implicit enumeration methods, or the design of heuristics. 74 Algorithms for 1/prec.SDST/Lmax In this section we shall present two algorithms developed to obtain solutions to l/prec,SDST/Lmax. The first is a branch and bound approach that makes use of the fact that l/prec,SDST/Lmax is equivalent to the problem of minimizing makespan in the presence of delivery times, l/preCjq^SDST/Cmax. The second is a dynamic programming algorithm which exploits the special structure of both the precedence constraints and the setup time matrix. A branch and b ound algorithm for 1/prec, q - ,SDST/Cmax Recall from Chapter III that the l/prec,SDST/Lmax problem can be transformed into an equivalent problem of minimizing Cmax in the presence of delivery times, l/prec,qj ,SDST/Cmax. In this section we describe a branch and bound algorithm to find optimal solutions to 1/prec , q } , SDST/Cmax . Following the approach of Carlier[20], with each feasible sequence for this problem we can associate a directed graph G - (X,U) . The node set X consists of a node for each operation ij carried out on the workcenter, plus a source node and a sink node *. The arc set consists of three types of arcs, u, , U 2 , and U 3 defined as follows: U, = the set of arcs (0,ij) whose cost is equal to except for the first operation ij in the sequence, for which it is s 0f1J , 75 U 2 = the set of arcs (ij,*) with costs p n + g fj , U 3 = the set of arcs (ij,kl) where ij immediately precedes kl in the sequence. These arcs have costs equal to Pfj + s ij, k r The maximum lateness of a feasible sequence is equal to the lenqth of a longest path in the associated graph G(X,U) . An example of such a graph is shown in Figure 5.2. The nodes have been numbered according to their occurrence in the sequence, with [i] representing the i'th operation in the sequence corresponding to this graph. Another important property of this graph is that the node corresponding to the operation with completion time equal to Cmax will be the node immediately preceding * on a longest path. Hence the problem of minimizing Cmax can be viewed as the problem of finding a sequence such that the length of the longest path in the corresponding graph G is minimized over the set of graphs corresponding to all feasible sequences. We can state the algorithm as follows: Algorithm BB: Step l: Let K ■ max { & u }. Calculate q.. = K - d-. for ijeN each operation ij . Step 2: Obtain an initial feasible solution by applying some heuristic to the problem. Set the upper bound UB to the value of Cmax for this solution. Let S denote the set of 76 n3 6 u H 09 Q CO U M h o js U | CM 01 U 3 60 77 operations available for sequencing, i.e., those whose predecessors have been sequenced. Let P be the partial sequence of operations already sequenced. Set S to be the set of operations without fixed predecessors, P = {}. This corresponds to the root node of the search tree. Step 3: Branch by appending each member of S in turn to the right of the partial sequence P associated with the current node. Step 4: For each new node generated at Step 2, perform the following: i) Calculate a lower bound LB as described below. ii) If LB > UB, fathom this node and go to step 5. Else, check if LB corresponds to a feasible solution. If so, set UB = LB. Update S by adding to it the successors of the last sequenced operation. Go to Step 5. Step 5: Select for further expansion the open ( i.e., not fathomed or already expanded) node with the lowest associated LB value. If no such node can be found, an optimal solution has been obtained. Else, go to Step 3. The lower bounds used for fathoming form one of the most critical components of any branch and bound method. We 78 will present two lower bounds that have been developed for 1/prec , qj , SDST/Cmax . Let us first consider viewing the q.. as a "teardown" time necessary to bring the machine to a final state after the completion of the last operation. Let us refer to this modified problem as (API) . The makespan of this problem will be given by n-1 ljeN 1=1 We have then the following propositions: Proposition 5.1 The optimal makespan for (API) is a lower bound on the makespan for 1/prec, qj, SDST/Cmax. Proof: Consider the graph G* corresponding to an optimal sequence S* to 1/prec, q. }l SDST/Cmax. There are two cases to consider: i) The operation with maximum lateness in S* is the last in the sequence. Then the longest path in G* is the path - [1] - [2] - . . . -[n-1] - [n] - *. Note that by its definition, an optimal solution to (API) will be the shortest path from to * containing all n nodes corresponding to operations. Hence, the path - [1] - [2] - ... -[n-1] - [n] - * in G must be the same as that 79 generated by the solution to (API) , otherwise it would not be optimal. Thus the objective function values of 1/prec, qj, SDST/Cmax and (API) are equal. ii) The operation with maximum lateness in S* is not the last operation. Then, since the objective function value corresponds to the length of a longest path in G*, the path - [1] - [2] - . . . -[n-1] - [n] - * cannot be a longest path in G . Since the optimal value of (API) corresponds to the length of the shortest path of this form, it must be less than the length of the longest path in G*, and hence the optimal value of 1/prec, q. } , SDST/Cmax. Q.E.D. Proposition 5.2 If the operation having maximum lateness in the sequence obtained from (API) is the last operation in the sequence, then the sequence is optimal to 1/prec , qj , SDST/Cmax . Proof: Construct the graph G corresponding to the sequence obtained by solving (API) , numbering nodes according to their position in the sequence. Since operation [n] has maximum lateness, the longest path in G is the path - [1] - [2] - ... - [n] - *, and the length of this path, Zp. + E s [i H i+i] + q [n] , is equal to the optimal value of (API). Since we know from Proposition 5.1 that the optimal value of (API) 80 is a lower bound on the optimal value of l/preCjq^SDST/Cmax, this sequence is optimal to l/pre^q^SDST/Cmax. Q.E.D. Problem (API) can be formulated as a Travelling Salesman Problem (TSP) as follows. Let the cities correspond to the node set of G. Let the arc costs represent the setup times Sjj jkl for nodes corresponding to operations, and q.. for arcs incident into node *. There are no arcs incident into node except one from node * that has cost 0, which is also the only arc incident out of that node. Thus we have ensured that the tour starts and ends in city 0, with city * the next to last city in the tour. The problem is to find the minimum cost tour starting and ending at node that visits all intermediate nodes exactly once. Since the TSP is known to be NP-hard, it is not computationally feasible to use it to develop bounds at each node of an implicit enumeration tree. Therefore it becomes necessary to find a tight lower bound on the optimal value of (API) which we could obtain with less computational effort. Such a lower bound is provided by the assignment relaxation to the TSP. This problem is solvable in polynomial time, and Balas and Toth[12] have found in an extensive study that this bound is a tight one for the TSP, on average yielding an optimal value equal to 99.2% of the optimal TSP value. It is important to note that the solution 81 generated by the assignment problem need not be feasible for (API) , since it may contain subtours and violate precedence constraints. Since the optimal value of the assignment problem is a lower bound on that of the TSP, then substituting the optimal value of the assignment problem for that of the TSP will still yield a lower bound on l/prec^. ,SDST/Cmax. Thus, if we denote the optimal value of the assignment relaxation of the TSP described above by A, then we have a lower bound LB1 given by LB1 = S p.. + A ijeN The lower bound LB1(P) for the partial seguence P at a given node of the enumeration tree corresponding to a partial seguence P is given by LB1(P) = M(P) + T + A(N\P) where M(P) denotes the makespan of the jobs in the partial seguence, T the total processing time of jobs in N \ P, and A(N\P) the assignment problem solved for the unseguenced jobs. A second lower bound, which will be referred to as LB2 , is obtained by relaxing the seguence-dependent setup times and seguencing operations in Earliest Due Date (EDD) order. The bound LB2 is set egual to the maximum lateness obtained from this seguence. 82 Dynamic programming algorithms for 1/prec.SDST/Lmax In this subsection we shall examine dynamic programming procedures for the 1/SDST/Lmax problem. We assume that there are m lots of chips to be processed, and that lot i reguires N(i) operations. Operations on the same lot are numbered in order of their precedence order. The total number of operations to be scheduled is n. Recall that we have a chain-like precedence graph since operations on separate lots are not linked by precedence constraints. This imposes a fixed ordering on the operations on the same lot. Given this ordering, we now give a dynamic programming procedure similar to that of Monma and Potts [78] to merge the operations on different lots together into an optimal schedule. Define f [n(l) ,n(2) , . . . ,n(m) , t, i] to be the minimum Lmax value for a partial schedule completed at time t containing the first n(k) operations of lot k, k=l,...,m where the last operation in the partial sequence comes from lot i. Initially, set f[0,0,0,...,0]=0 and all other values to infinity. The optimal Lmax value will be the smallest value of the form min { f [N(l) ,N(2) , . . . ,N(m) ,T,i] } where l<i<m m N(i) m T < 2 £ p.. + s N(i)s — . . *j" . l ' max 1=1 3=1 1=1 and s max denotes the maximum setup time value. The function values can be computed using the following recursive relation: 83 f[n(l) ,n(2) ,...,n(m) ,t,i] = min{ max {t-d . . , f [n' (1) ,n» (2) , . . . ,n- (m) , t • ,k] } } l<k<m where n'(j) = n(j) for j^i, n 1 (i) - n(i)-l and t'=t-o - s The number of possible states in this dynamic program is m(N+l) m T, where N = max,{N(i)}, and the value of each state is calculated in 0(m) steps. Hence the computational complexity of this procedure is 0(m 2 (N+l) m T) . When setup and process times are large, the large values of T will result in rapid growth of the state space and thus of storage requirements. However, we observe that the completion time t of any partial schedule will consist of two components, the processing times of the operations in the partial sequence and the setup times taking place between operations. This enables us to take advantage of the special structure of the semiconductor testing environment. An important characteristic of the production equipment in use is that there are a limited number, generally less than ten, of distinct entries in the setup time matrix. This is much less than n , the number of possible entries in the setup matrix. Let the total number of distinct setup time values s(k) be S. Define f [n(l) ,n(2) , . . . , n(m) ,a 1 , o 2 , . . . , a s , i] to be the minimum Lmax value for a partial schedule containing the first n(k) operations of lot k, k=l, . . . ,m and o- occurrences 84 of the j'th distinct setup time value s(j) , j=l,...,S where the last operation to be processed belongs to lot i. We can now calculate the completion time t of the partial sequence from the relation m n(i) S t = 2 s p.,- + Sa k s(k) i=l j=l k=l Initially set f[0,0,...,0,0] = and all other values to infinity. The optimal value will be the smallest value of the form min { f [N(l) ,... ,N(m) ,<?.,, a 2 , ... ,a s , i] } where E^a^n. The l<i<m recursive relation can now be written as f[n(l),n(2),...,n(m),(j 1 ,o 2/ ...,a s ,i] - min{ max {t-d n(1 , , f [n» (1) , . . . , n' (m) ,a\, . . . ,ff« 8 ,k] } } l<k<m where t is as calculated above, a ] = a' } if s (n , (k)#k)f(n<!)#n f s(j) and fft J = CTj - 1 if ■ (n , <k)fk)f(n(l)fi) = s(j). The number of states in this dynamic program is at most m(N+l) m n s , where N = max f {N(i)}, and the value of each state is computed in 0(m) steps. Hence the complexity of this procedure is (m 2 (N+l) m n s ) . It is interesting to note that the complexity of these procedures is polynomial in the number of operations but exponential in the number of lots. Thus, when the number of lots is fixed, l/prec,SDST/Lmax can be solved in polynomial time. When the number of lots is small and the number of 85 operations on each lot is large, this procedure may provide a practical alternative to branch and bound. However, as the number of lots increases, the computational burden increases rapidly. Heuristic Procedures for 1/r . ,prec .a j , SDST/Cmax In this subsection we will first examine the worst-case performance of a certain class of one-pass heuristics, list- scheduling procedures, for 1/rj ,prec, qj , SDST/Cmax. For the sake of simplicity in this section we shall use only a single subscript to represent operations, taking the lot structure into account explicitly as precedence constraints. We shall then examine the behavior of a member of this class that has been extensively studied in the context of the problem without setup times, the Extended Jackson's Rule[20.85], for the special case of the problem where release times and due dates are agreeable, i.e., r,- < r- implies d f < d, . We can define the family of list-scheduling algorithms as follows: Algorithm LS: Whenever the machine is free and there are one or more available operations, select one of the available operations and sequence it next. 86 An operation i is said to be available at time t if r ; < t and all predecessors of operation i have already been sequenced at time t. Note that which of the available operations is to be selected can be specified in different ways. Examples of selection criteria resulting in different list-scheduling heuristics might be to select the operation with earliest due date or shortest processing time. Due to the presence of release times the schedule obtained by Algorithm LS will consist of one or more blocks, periods of time in which the machine is continually busy, either in processing or in setup. Let C(LS) denote the maximum completion time of the sequence obtained by Algorithm LS. Let [k] denote the k'th operation in the sequence, and [j] be the operation such that its completion time is equal to C(LS) . Then j-l J C(LS) = r m + S s [h][h+1] + S p [h] + q h=i-l h=i for some operation [i], before whose arrival the machine is idle. Proposition 5.3: Let C(LS) be the value of the schedule obtained from LS for the l/r^pre^q^SDST/Cmax problem, and C* the optimal value of l/rj,qj/Cmax, the problem without setup times. Then C(LS) < 3C*, and this bound is tight. 87 Proof: As discussed above, j-l J C(LS) = r [n + S s [h][h+1] + S p [h] + q h=i-l h=i By construction of the sequence, operation [i] is available no later than operation [j], which means that either r m < r^, or r [<3 > r t , 3 and i precedes j. However, the latter case is impossible since if i precedes j then they must be operations performed on the same lot, which means that r [f] = r cj] . This contradicts the assumption that r cn > r [j] • Tnus ' we conclude that r m < r ry] . j-l j C(LS) < r cj] + 2 s [h][h+1] + 2 p [h] + q h=i-l h=i j-l j-l '[j] + P[j] + 5[j] + 2 . S [h ][h+ 1] + s . P [M h=i-l h=i The first three terms clearly constitute a lower bound on C . Each of the latter two terms is less than or equal to the sum of the processinq times, which in turn is a lower bound on C*. Thus, C(LS) < 3C*. We now provide an example to show that this bound is tight. Consider an instance without precedence constraints and with the following parameters: 1 r i Pi 5f 1 n 2 1 1 n 88 where s 12 = n, s 21 = 1. Let all other s,, values be equal to 0. Algorithm LS will yield a sequence {1,2} with completion time 3n+l. However, the optimal sequence for the problem without setup times is {2,1} with completion time n+2 . Thus, C(LS)/C* approaches 3 as n becomes large. Q.E.D. Remark: Proposition 5.3 is also true for the problem without precedence constraints. A particular member of the class of list-scheduling algorithms is the Extended Jackson's Rule studied by Potts [85] and Carlier[20] . This algorithm can be stated as follows: Algorithm EJ: Whenever the machine is free and there are one or more available operations, sequence next the operation with largest value of q. . Let [k] denote the k'th operation in the sequence, and [j] be the operation such that its completion time is equal to C(EJ) . Then j-l J C(EJ) = r m + Z s [h][h+1] + s p [h] + q h=i-l h=i for some operation [i], before whose arrival the machine is idle. 89 It is clear from Proposition 5.3 that for the general l/r jf prec f q i# SDST/Cmax problem, C(EJ) < 3C*, where C* is the optimal value of l/z-j ,qj/Cmax. However, for a special case of the problem we have the following result: Proposition 5.4: Suppose r s > r t implies d s > d t and thus q s < q t and s fj < p. for all jobs i,j. Let c(EJ) be the value of the sequence obtained by Algorithm EJ, and C* the optimal value of l/r^qj/Cmax. Then C(EJ) < 2C* , and this bound is tight. Proof: By construction of the sequence, r m = min k {r k ), ke{ [i] , . . . , [ j ] } , by the argument in the proof of Proposition 5.3. For any ke { [i] , . . . , [ j ] } , suppose q tj] > q [k] . It is impossible for [j] and [k] to be operations on the same lot since in that case we would have q cj] = q [k] . Hence [k] and [j] are not operations on the same lot, i.e., they are not linked by any precedence constraints. Since [k] is processed earlier than [j], this means either q [k] > q tJ] or r [k] < r rj] , which by the assumption of agreeable arrival times and due dates implies q [k] > q fj] . Both these cases contradict the assumption that q [j;| > q [k] . Hence, we conclude that q. ] = min k {q k }. It has been shown by earlier [20] that for any subset I of the operations to be sequenced, 90 H(I) = minlr,-} + 2 p. + minlq,. } iel iel iel is a lower bound on the optimal value of 1/rj ,qj/Cmax, the problem without setups. Setting 1= { [i] , . . . , [ j ] } , we see j-l J C(EJ) = r [n + 2 s [h][h+1] + 2 P[h] + q h=i-l h=i j j-l * r m + J Pm + q C j] + s S [ h] [h + 1] h=i h=i-l j j * r m + s Pew + <3[j] + s Pi h=i h=i < 2C To see that the bound is tight, consider the following example: 1 r i Pi <3i 10 n 1 2 In where s 12 = n and s 21 = 0. Algorithm EJ returns a sequence of {2,1} with C(EJ) = 2n+2. The optimal solution without setups is also {2,1} with C* = n+2 . Thus we see that C(EJ)/C* tends to 2 as n becomes large. Q.E.D. Corollary 5.1: Let L(EJ) denote the value of Lmax of the sequence obtained by applying Algorithm EJ to the corresponding 1/rj , qj , SDST/Cmax problem, and L* the optimal value of 1/rj/ Lmax. Then L(EJ) < 2L* + d max , where d max = max^d,-}. 91 Proof: Note that for a given sequence, the values of Cmax obtained in l/r^qj ,SDST/Cmax and Lmax obtained in l/r^SDST/Lmax will differ by the constant K - max^d,}. Similarly, for the problem without setup times, C* and the optimal Lmax value L* will differ by K. Thus, L(EJ) + K < 2L + 2K. After simplification, the result follows since K=d max- Q.B.D. In order to obtain further improvements over the sequences generated by the above heuristics, the neighborhood search procedure described in the next section can be applied to the solutions obtained. A Neighborhood Search Algorithm The algorithm developed in this section is a neighborhood search procedure that finds a local optimum. It is based on insights obtained using the disjunctive graph representation described previously in Chapters III and IV. These insights enable us to ensure that only feasible neighboring solutions are generated by the procedure at each step. The approach used here makes use of the following result [53] : Theorem: Let 0. , 0. j denote the location in the current sequence of jobs i and j. The reversal of a disjunctive arc 92 between i and j cannot lead to a cycle if and only if the two operations are adjacent in the sequence, i.e., either 0- = Oj + 1 or 0j = 0. + 1. This tells us that feasibility is maintained by reversing only disjunctive arcs between adjacent operations in the sequence. Note that this corresponds to a pairwise exchange between operations that are adjacent in the sequence and have no precedence constraints. This renders explicit consideration of the disjunctive graph representation of the workcenter unnecessary. The algorithm presented here uses this property as a basis for a neighborhood search procedure. An initial feasible solution is generated using a heuristic. The set of pairwise exchanges between adjacent operations in this sequence is examined, and those leading to an improvement of Lmax are used to generate neighboring sequences. This procedure is then applied in turn to all neighboring sequences until no further exchanges leading to improvement can be found. The neighboring sequences generated at each stage are checked to ensure they have not been examined already in order to prevent cycling. The final solution returned by the algorithm is the best sequence encountered during the search. Since we have a single machine, and assuming n operations, we have at most (n-1) exchanges to consider at any stage of the search. 93 In order to determine whether an exchange will lead to a poorer solution, consider two adjacent operations i and j in the current sequence. Let kp be the operation preceding im in the current sequence, and lq the operation succeeding jn. The Gantt chart is as follows: Current schedule: A kp im jn lq B im, jn After exchange of im and jn: A kp jn im lq B jn, im Let C fB j n denote the earliest start time of operation lq before the exchange, and C jn - m the earliest start time after the exchange. C • = im,jn fc A + Pkp + S kp,im + Pim + S im,jn + Pjn + S jn,lq C jn,im = fc A + Pkp + S kp,jn + Pjn + S jn,im + Pim + S im,lq D " C im,jn " C jn,im = ( S kp,im + S im,jn + S jn,lq) ( S kp,jn + S jn,iin + S im,lq) Clearly, when D > 0, carrying out the exchange cannot make Lmax worse, unless Lmax = L- . ' im Thus, an exchange cannot worsen the current solution 1) if D > 0, and 94 2) if the delay in the completion of im is less than Lmax - L- . im We can state the algorithm as follows: Algorithm NBHD: Step 1: Generate an initial feasible solution by seguencing all lots in ascending due date order, with the operations on each lot in order of precedence. Set UB to the value of Lmax for this seguence. Record this seguence in BEST. Step 2: Examine each of the (n-1) possible pairwise exchanges in the current seguence. If the exchange meets any of the following conditions, ignore it: - It is infeasible due to precedence constraints - It leads to a poorer solution - It leads to a seguence that has already been generated If there are no exchanges leading to improvement, select another seguence whose neighbors have not been examined and repeat Step 2. If no such seguence exists, stop. Return seguence in BEST as final solution, with objective function value UB. Step 3 : Generate the seguences corresponding to the exchanges determined in Step 2 and record them. If any seguence generated has a better objective function value than UB, record that seguence in BEST and update UB. Select 95 a sequence whose neighbors have not been examined and go to Step 2 . Another way of looking at what this algorithm attempts to do is to view it as trying to reduce the maximum lateness by reducing the completion time of the latest lot. This is equivalent to solving a travelling salesman problem considering only the operations in the sequence up to the latest operation. Viewed from this perspective, the algorithm can then be described as a 3 -exchange procedure where we examine combinations of three arcs (with costs s kp,im' s im,jn and s jn,iq) and tr Y to replace them with a shorter three-arc combination (with costs s. . , s ; „ , and s. . ) . N kp,jn' jn,im im,lq' Minimizing Number of Tardy Lots In the context of semiconductor testing, the lateness of the entire lot, not of any individual operation is of interest. Thus for the rest of this section we will use the notation SU,- to denote number of tardy lots, as opposed to individual operations. The lot structure is indicated by the presence of precedence constraints between operations on the same lot. Thus, l/preCjSDST/SU, will denote the problem of minimizing the number of tardy lots in the presence of precedence constraints between operations on the same lot and sequence-dependent setup times. 1/SDST/SU,. will be used to represent the special case where there are no precedence 96 constraints, i.e., each lot requires only one operation. Recall from Chapter III that even the 1/prec/SU,- problem is NP-hard[72]. Hence we shall concentrate on developing a heuristic procedure for l/prec,SDST/EU. and examining its worst-case behavior for a special case. A Heuristic Procedure for l/prec,SDST/SU . In this section we shall present an algorithm similar to that of Moore cited in Baker [3] for the 1/prec, SDST/EU,- problem. This algorithm is based on certain relations that exist between the problems of minimizing maximum lateness and that of minimizing the number of tardy jobs. We shall use the term "Lmax-optimal" to denote a sequence which minimizes Lmax, and "ZU,. -optimal" to denote a sequence which minimizes the number of tardy lots. Moore's algorithm[3] is based on the fact that any optimal solution will consist of a set A of jobs that are on time, whose sequence minimizes Lmax over that set, and another set T of tardy jobs sequenced after A whose sequence is immaterial. Once the algorithm has determined that there does not exist a sequence with EU^O, it proceeds to construct the set T of tardy jobs by assigning to T the job in the sequence up to the first tardy job that has the longest processing time. Moore proves that there is no way the jobs in the sequence up to the first tardy job can be sequenced so that none are tardy. The idea behind the 97 algorithm is that given one job has to be late, assign to T the job that will allow those remaining to start as early as possible. For the rest of this section, we will assume that for all operations i,j,k the setup times satisfy the triangle inequality, i.e.,s jk < s fi + s jk . This ensures that removing an operation from any sequence does not result in later completion times for the remaining operations. Proposition 5.5: If setup times satisfy the triangle inequality, then an optimal sequence S will have the form (A,T) , where lots A are on time and in an Lmax-optimal sequence and those in T are tardy. Proof: Let T be the set of tardy lots. Resequence S so that the sequence of operations for lots in A is maintained relative to one another, and the operations on lots in T are at the end of the sequence in any feasible order. In order to do this it may be necessary to move an operation jeT out from between two operations i,keA. However, since setup times satisfy the triangle inequality, removing an operation j from the sequence cannot result in increased completion times for the remaining operations. Hence the operations in A start no later than they did before resequencing, so no more jobs are tardy now than were in S. Since no lot in A is tardy, Lmax < for this 98 sequence. Hence resequencing the operations in A so as to minimize Lmax cannot increase Lmax. Thus, the number of tardy lots in the rearranged sequence is no greater than that in S, and so we have obtained an optimal schedule of the desired form. Q.E.D. Given this result, if we had a means of deciding which lot to assign to T given an Lmax-optimal sequence, we could construct an Su^-optimal sequence in the same fashion as Moore. However, this is not possible due to the presence of sequence-dependent setup times. In the presence of setups, it is no longer the case, for example, that there does not exist a sequence of the operations up to the first tardy- operation in an Lmax-optimal sequence where none are late. One can, however, prove the following: Proposition 5.6: If in the sequence up to the first tardy operation in an Lmax-optimal sequence with Lmax > there exist three consecutive operations i, j, k such that s r + p. + s jk ~ s ik - Lma x, then there exists an EUj-optimal sequence in which only the lot containing operation j is tardy. Proof: Since in the original sequence Lmax > 0, at least one operation must be tardy in the SU, -optimal sequence. Suppose we delete the lot containing operation j from the sequence and maintain the relative sequence of all other 99 operations. Then the completion time of all operations to the right of j in the sequence will decrease by at least s- , + Pj + s Jk - s ik units of time, which is greater than or equal to Lmax. Since there are no tardy operations to the left of j this will result in Lmax < for the new sequence. If we append the lot containing operation j to the end of the new sequence, we have a sequence with 2Uj=l. Since at least one lot has to be tardy, this sequence is EUj-optimal . Q.E.D. Noting that we are concerned with minimizing the number of tardy lots and not the number of tardy operations, instead of assigning operations to T we will assign entire lots. Hence the time saved by deleting a lot m from the sequence is the sum of the savings obtained by dropping all operations in that lot. Based on these insights, we can construct a heuristic closely paralleling Moore's Algorithm in operation. The algorithm can be stated as follows: Algorithm NTH: Step 1: Obtain a solution to the Lmax problem. If this Lmax value is nonpositive, go to Step 3. Step 2: Examine the subsequence up to the first tardy operation . Delete the lot that results in the largest time savings. Go to Step 1. Step 3: Construct the final sequence by taking the 100 Step 3 : Construct the final sequence by taking the current given by Step 1 and appending to the end all deleted lots with their operations in any feasible order. In order to implement this algorithm, it is necessary to have available an algorithm to solve the problem of minimizing Lmax. In theory, the exact algorithms presented earlier in this chapter could be used for this purpose. However, use of a heuristic together with the neighborhood search procedure presented in the previous section might also yield good solutions with much less computational burden. Worst-Case Analysis for l/SDST/SU - We will now examine the worst-case behavior of the algorithm for the case without precedence constraints, i.e., where each lot requires only one operation. Thus the terms "lot" and "operation" are equivalent in the context of this problem. We shall assume that the Lmax problem in Step 1 of Algorithm NTH is solved optimally yielding an Lmax value of L at the first iteration, and that s,.. < Pj for all i and j . The latter corresponds to assuming that it takes no longer to set up the test equipment for an operation than it does to perform the operation, which is indeed the case in practice. We have the following Lemmas: 101 Lemma 5.1: Let L(S) be the optimal Lmax value for a set S and L(S') be the optimal Lmax value for the set S' obtained by adding one lot, say lot k, to S. Then L(S') < max {0,L(S)} + 3p max , where p max is the maximum processing time of all lots in S ' . Proof: Let R be the sequence corresponding to L(S) . Then the sequence obtained by assigning lot k in the first position followed by the other lots in the same sequence as in R is a feasible sequence for S 1 . For all lots in R the lateness will increase by at most 3p max , since s. } + p. + s jk - s- k < 2 Pj + P k < 3p max for any i,j,k. Since the latest possible completion time of lot k in the new sequence is 2p max , L k < 3p max . The result follows. Q.E.D. Corollary 5.2: Let L be the optimal Lmax value obtained at the first iteration. Then L/3p max is a lower bound on the optimal number of tardy lots SU-*. Proof: If L < then there are no tardy lots and we are done. For the other case, SU,* > 0. Suppose SU-* is less than L /3p max - Let SU,-* = L/3p max - k, where k > 0. By Proposition 3, the optimal sequence corresponding to SU,-* contains two sets A and T of early and tardy lots respectively. Repeatedly applying Lemma 1 by placing the lots in T in front of the lots in A we obtain a sequence S having maximum lateness 102 less than or equal to 3p max (L/3p max - k) < L, which contradicts the optimal ity of L. Q.E.D. Lemma 5.2: Let L be the optimal Lmax value obtained at the first iteration. Then rL/P m j n l is an upper bound on the number of tardy lots yielded by Algorithm NTH if setup times satisfy the triangle inequality. Proof: Since setup times satisfy the triangle inequality, when a lot in the subsequence up to the first tardy lot is dropped at least p min units of time will be saved. Thus r L /P min l gives the maximum number of lots that would need to be dropped to have Lmax < 0. Q.E.D. Proposition 5.7: Let SU f be the number of tardy lots given by the algorithm above where the Lmax problem in Step 1 is solved optimally and SU-* the optimal number of tardy lots. Then we have SU, < i-3/JSU^ , where fi = P max /p min . Proof: Noting that by the Lemmas above, L/3p max < ZU* < EIL < rVP rain l we see that ZU, < pL/P mi - n l = r 3/?L/3p max1 < rSjSSU^n Q.E.D. 103 Dynamic programming procedures for 1/prec.SDST/SU j In this section we examine a dynamic programming procedure for l/prec,SDST/SUj which again takes advantage of the special chain-like structure of the precedence constraints. Again assume that operations are indexed according to their order in the lot. Again there are m lots, each lot requiring N(i) operations, the total number of operations to be scheduled is n and N ■ max, {N(i)}. Since we are concerned with the number of tardy lots and not the number of tardy operations, we shall assign a weight w-- = to all operations except those which are the last operation to be performed on a lot, which will be assigned a weight equal to 1. Let f [n(l) , . . . , n(m) , t, i] be the minimum weighted number of tardy operations in a partial sequence containing the first n(k) operations of lot k where the last operation in the partial sequence belongs to lot i and is completed at time t. Initially, set f[0,...0,0] = and all other values to infinity. The optimal value will be the smallest value of the form min { f [N(l) , . . . ,N(m) ,T,i] } where l<i<m m N(i) m T < Z Z Pjl . + S N(i)s max 1=1 n=l 1=1 The recursive relation can then be defined as follows: 104 f [n(l) , . . .,n(m) ,t,i] = min { f [n 1 (1) , . . . ,n" (m) ,t' ,k] ), if t < d, Kk<m min { f[n' (1) , . . . ,n« (m) ,f ,k] + w n(i) , }, if t > d- Kk<m where n'(j) = n(j) for j^i, n 1 (i) = n(i)-l and =t ~Pn(i),i " S (n'(k),k),(n(i),i) The number of possible states in this dynamic program is m(N+l) T, and each state is evaluated in 0(m) steps. Thus the computational complexity of this dynamic program is 0(m 2 (N+l) mf1 T) . Again, as was the case for 1/prec, SDST/Lmax, the presence of the T term leads to rapid growth in the number of states and thus storage requirements as the process and setup times get large. As was the case for the 1/prec, SDST/Lmax problem, we can exploit the special structure of the setup time matrix to alleviate this problem. Again assume that we have S distinct setup time values s(k), k=l,...,S. Then we can define f [n(l) ,n(2) , . . . ,n(m) , ct 1 ,ct 2 , . . . ,a s , i] to be the minimum weighted number of tardy operations for a partial schedule containing the first n(k) operations of lot k, k=l,...,m and CTj occurrences of the j'th distinct setup time value s(j) , j=l,...,S where the last operation to be processed belongs to lot i. Initially set f[0,0,... ,0,0,0] = and all other 105 values to infinity. The optimal value will be the smallest value of the form min { f [N(l) , . . . ,N(m) ,a 1f a 2 , . . . ,CT s ,i] } where T,.o^=n. The l<k<m recursive relation can now be written as f [n(l) ,n(2) , . . . ,n(m) ,o u o 2 , . . . ,a s ,i] - min { f[n , (l),...,n , (m),a , 1 ,ff , 2 ,...,a , s ,k] }, t< d 1 l<k<m min { f[n« (1) ,...,n' (m) ,o' u o' 2 , . . . ,a' s ,k] + w n<i) , }, t>d,- l<k<m where a j - fl'j if s (n , <k>fk>f(n(f)J) f s(j) and a' j = a ] - 1 if S (n'(k),k),(n(i),i) = S (D) • The number of states in this dynamic program is m(N+l) m n s , and each state is evaluated in 0(m) steps. Hence the computational complexity of this procedure is 0(m 2 (N+l) m n s ) . Again, as was the case for the 1/prec, SDST/Lmax problem, the complexity of the procedure is polynomial in the number of operations and exponential in the number of lots. It is also interesting to note that the dynamic programming procedures for both 1/prec, SDST/Lmax and 1/prec, SDST/EU- have the same complexity. This is unusual since SU 1 is generally a much more difficult performance measure to minimize than Lmax. 106 Summary In this chapter we have presented formulations, complexity classifications and solution procedures for a family of problems based on the modelling of workcenters consisting of a single tester. These problems turn out to be NP-hard, but also in a number of instances to have interesting theoretical properties. For the problem of minimizing maximum lateness when all jobs are available simultaneously, we have presented a branch and bound algorithm and dynamic programming procedures. The branch and bound algorithm has been shown to be capable of solving problems with up to 15 operations in reasonable computer time. The dynamic programming procedures are polynomial in the number of operations, but exponential in the number of lots. Thus when the number of lots is small, these procedures may provide a good alternative to the branch and bound algorithm. Heuristics have been developed for the problems of minimizing Lmax with non-simultaneous job arrivals and minimizing number of tardy lots when all jobs are available simultaneously. For the former problem, tight absolute error bounds have been developed and a neighborhood search procedure outlined to further improve the solutions obtained from the heuristics. For the latter problem, a data- dependent worst-case bound has been developed for a special case. 107 Dynamic programming procedures have also been developed for the problem of minimizing number of tardy lots. These procedures are similar to those developed to minimize Lmax and have the same complexity, which is unusual since number of tardy jobs is generally a more difficult performance measure to optimize. CHAPTER VI BATCH PROCESSING MACHINES Introduction In this chapter we examine the problem of scheduling batch processing machines. A batch processing machine is defined to be a machine where a number of jobs can be processed simultaneously as a batch. The processing time of a batch is egual to the longest processing time among all jobs in the batch. Once processing is begun on a batch, no job can be removed from the machine until the processing of the batch is complete. By contrast, we shall refer to a machine capable of processing only one job at a time as a unit-capacity machine. These problems are motivated by burn-in operations in the semiconductor industry, where lots of chips are placed in ovens and subjected to thermal stresses for an expended period of time in order to bring out latent defects leading to infant mortality before the product goes to the customer. In order to be processed on the batch processor, integrated circuits are loaded onto boards, which are then loaded into the ovens. A certain type of integrated circuit 108 109 may require a product specific board, or a particular oven. Each board can hold a certain number of chips, and each oven a certain number of boards. Thus the problem of scheduling this kind of operation is complicated by the fact that oven and board availabilities have to be taken into account to produce a feasible schedule. The processing times in burn-in operations are generally extremely long compared to other testing operations (e.g., 150 hours as opposed to 4-5 hours in testing) . Thus the efficient scheduling of these operations is of great concern to management. Management objectives are primarily concerned with customer service and resource utilization. Hence we examine the performance measures of maximum tardiness (Tmax) , number of tardy jobs (SU,.), total flow time (SF f ) and makespan (Cmax) . In this chapter we present efficient algorithms for minimizing a number of different performance measures on a single batch processing machine. We also provide an algorithm to minimize total flowtime on parallel identical batch processing machines, and extend the Longest Processing Time (LPT) heuristic developed to minimize makespan on parallel identical processors to the case of parallel batch processing machines. Assumptions and Notation We shall assume in this chapter that all jobs are of the same size, i.e., require the same oven capacity, and that 110 the oven can process at most B jobs at the same time. In practice this is achieved by splitting large lots into lots compatible with available capacity before processing on the batch processor. Once processing of a batch is initiated, it cannot be interrupted and other jobs cannot be introduced until processing is completed. With each job i we shall associate a processing time p i ,a due date d- and a release time r- which corresponds to the time the job becomes available for processing on the batch machine. In order to be able to refer to the problems under study in a concise manner, we shall again use the notation of Lageweg et al. [59,60], extended to include batch processing machines. The use of the letter B in the second field of the notation will represent the fact that the machine or machines being scheduled are batch processing machines. Some examples of the extended notation are as follows: 1/B/Cmax: minimize makespan on a single batch processing machine. l/r.,Pj=p f B/SUj : minimize number of tardy jobs on a single batch processing machine where all jobs have egual processing times and job i is available at time r ■ . We will also need the following definitions: Definition 6.1: We say a seguence is in batch-EDD order if for all batches P,Q in the seguence where batch P is Ill processed before batch Q, there is no pair of jobs i,j such that ieP, jeQ and d,- > dj. Definition 6.2: We say a sequence is in batch-LPT order (batch-SPT order) if for all batches P,Q in the sequence where batch P is processed before batch Q there is no pair of jobs i,j such that ieP, jeQ and p } < p- } (p. > Pj) . These definitions will enable us to define properties of optimal solutions that can be used to derive optimal algorithms for a number of batch scheduling problems. Minimizing Total Flowtime The first problem we examine is that of minimizing total flowtime on a single batch processing machine when all jobs are available simultaneously. We shall denote this problem by 1/B/2F- . This problem cannot be viewed as a special case of the serial system consisting of a unit- capacity machine and a batch processing machine examined by Ahmadi et al.[2] due to the fact that the processing time of a batch is not independent of the jobs composing it. In this section we shall reindex the jobs in ascending order of processing times . We have the following result: Lemma 6.1: In the 1/B/SF,- problem, there exists an optimal solution where jobs are in batch-SPT order. 112 Proof: Consider an optimal sequence and suppose we have a batch P processed immediately before Q such that max {p k |keP} > max {pJkeQ}. Then reversing the sequence of the two batches will improve SF- . Suppose after performing this exchange for all batches in the sequence we have two jobs i,j such that p. < p } and jeR, ies where batch R is processed before batch S. Suppose we move i to R, j to S. Since p. < Pj. , the completion time of R is not increased. Since we have rearranged the batches in ascending order of processing time, we know that max {pJkeS} > max {pJkeR}, it is impossible for the completion time of batch S to be delayed by replacing a job in S with a job from R. Repeating this procedure we will obtain a solution of the desired form. Q.E.D. Based on this property we can develop a dynamic programming procedure to solve 1/B/SF, . As a result of Lemma 6.1, we can view this as a consecutive partition problem. Recall also that we have reindexed the jobs in order of increasing processing time. Hence the processing time of a batch will be equal to the processing time of the highest indexed job it contains. Due to the fact that once processing on a batch starts, no job can be removed until the batch is completely processed, the completion time of all jobs in a batch is equal to the completion time of the batch. Given these insights, we can state the algorithm: 113 Algorithm DPI: Let f(j) denote the minimum total flow time for a schedule containing jobs l,...,j. Let F(j) denote the finishing time of the sequence corresponding to f(j). Initially, f(0)=0, F(0)=0 and f(i)= °o , F(i)=°o for i<0. Then f(j) = min { f(j-k) + k(F(j-k) + p.) } l<k<B F(j) = F(j-q) + p. where q = {i|f(j) = f(j-i) + i(F(j-i) + p } ) } . The optimal value will be given by f (n) . The number of states in this dynamic program is n, and each state is evaluated in 0(B) steps. Hence the complexity of this procedure 0(nB) . Minimizing Maximum Tardiness In this section we present efficient algorithms to minimize Tmax on a batch processing machine. We note that when B=l, the problem is equivalent to the unit-capacity machine problem, l/r./Tmax, which is NP-hard in the strong sense [59,60]. Hence the general 1/r- ,B/Tmax problem is NP- hard. We will first consider the case where all processing times are equal, which we will denote by 1/r, ,p,=p, B/Tmax. In addition we assume that release times and due dates are agreeable, i.e., r. < rj implies d- < d,. The problem of determining whether a feasible schedule, i.e., a schedule 114 with Tmax=0 exists for this problem was addressed by Ikura and Gimple[56]. We present an alternative dynamic programming algorithm to determine whether or not a feasible schedule exists and then use it to develop a polynomial time procedure for minimizing Tmax. We apply a similar approach to the problem where all jobs are available simultaneously and processing times and due dates are agreeable. The approach we use is similar to that of Simons [37] for the l/rjjPj^p/Lmax problem. We develop an O(nB) dynamic programming algorithm that will find the feasible seguence with minimum completion time if one exists. We then use a bisection search over possible values of Tmax to obtain the optimal Tmax. Throughout this section we assume that jobs are indexed in increasing order of due dates . We have the following result: Lemma 6.2: In the 1/r- ,p.=p,B/Tmax problem with agreeable due dates and release times, if a solution with Tmax=0, exists, then there exists a solution with Tmax=0 where the jobs are in batch-EDD order. Proof: Suppose there exists a feasible solution such that we have two batches P and Q where P is processed before Q and there are two jobs i and j such that jeP, ieQ and d- < d-. Let r(P) = max{r k |keP} and r(Q) = max{r k |keQ}. Then the 115 completion times of these batches are C(P) = max{r (P) , C (P- !) } + P/ C(Q) = max{r(Q) ,C(Q-1) }+p respectively, where C(P- 1) and C(Q-l) denote the completion times of the batches preceding P and Q. Suppose we exchange i and j by moving j to Q and i to P. Since d,. < dj , r f < r } < r(P) and r, < r, < r(Q) and the start of processing on neither batch is delayed as a result of the exchange. Since all jobs have the same processing times, the completion times of the batches after the exchange C'(P) and C'(Q) will not be greater than C(P) and C(Q) respectively. Since the original schedule was feasible, C(Q) < d,- and C(P) < dj which implies C'(Q) < C(Q) < d, < dj. Since P is processed before Q, and C'(P) < C(P) < C(Q) < d,- . Hence the new schedule is also feasible. Q.E.D. We can now state the dynamic programming algorithm DP2 which will find a feasible schedule with minimum makespan if a feasible schedule exists as follows. Algorithm DP2 : Let f(j) denote the minimum finishing time for jobs l,...,j. Then f(0) = 0, f(j) = oo for j < 0. f(j) = min{fj(j) Ij-B+I < i < j}, where 116 max{f (i-1) ,rj}+p, if max{ f (i-1) , r^+p < d i f i(j) " \ oo , otherwise denotes the completion time of jobs 1 through j when jobs i,i+l,...,j are processed in the last batch. If f(j) > d, , then it is impossible to schedule jobs l,...,j so that none are tardy, so we set f(j) = °°. In order to justify algorithm DP2 , note that each batch will contain no more than B consecutively indexed jobs due to the property proven in Lemma 6 . 2 above . Thus the problem becomes a consecutive partition problem. In order to be feasible, we must have max{ f (i-1) , r, }+p < d k , for all i<k<j in order for the due dates to be met and since jobs are indexed in ascending order of due dates, this is implied by max{f (i-1) ,rj}+p < d- . We also reguire j-B+1 < i < j since the maximum number of jobs that can be processed in a batch is B < n. There are n states in this dynamic program, and each state is evaluated in 0(B) operations. Hence the time complexity of Algorithm DP2 is 0(nB). Given that we have the above algorithm for determining whether or not a feasible solution exists, we can use the following approach to minimize Tmax: 117 Algorithm TMAX1: Step It Apply algorithm DP2 to the problem. If a feasible solution is found, stop. Tmax =0. If an infeasibility is encountered, i.e., f(j) = » for some j, then construct any sequence. Set UB to be the value of Tmax for this sequence, and LB = 0. Step 2: If |UB-LB| < e, stop. Otherwise, augment all the due dates by the quantity (UB+LB)/2 and apply algorithm DP2 . If a feasible solution is found, set UB=(UB+LB)/2 and repeat Step 2. If an infeasibility is encountered, set LB=(UB+LB)/2 and repeat Step 2 . The complexity of this algorithm will be 0(nBlog 2 D), where D denotes the width of the search interval of the bisection search. Clearly the lower limit of this interval is zero, corresponding to a feasible schedule. The upper limit of the interval can be determined from any sequence as we did in Alqorithm TMAX1 or from the following result: Lemma 6.3: In the l/rjjp^p^/Tmax problem with agreeable release times and due dates, (n-l)p is an upper bound on the value of Tmax. Proof: Since we have n jobs to be scheduled, we can have no more than n batches in any schedule. When a given job j 118 arrives, it can thus have at most (n-1) jobs that have arrived before it. Thus it will wait at most (n-l)p time units before being processed. Since by assumption r,+p<d-, if dj is augmented by (n-l)p, job j will always be on time with respect to this new augmented due date. Q.E.D. Corollary 6.1: The time complexity of Algorithm TMAX1 is 0(nBlog 2 [(n-l)p]) . Proof: Follows directly from Lemma 6.3. Q.E.D. We now address the problem of minimizing Tmax on a batch machine where all jobs are available simultaneously, process times are arbitrary but process times and due dates are agreeable, i.e., p- < pj implies d- < dj . This assumption is a generalization of several endogeneous due date assignment rules discussed by Cheng and Gupta[25]. An endogeneous due date assignment rule is one where the scheduler assigns a due date to each job as it arrives on the basis of job characteristics, shop status and estimated flow time through the shop. This scenario is guite realistic in the semiconductor manufacturing context, since due dates for orders are set through a process of negotiation between the customer and the manufacturing facility. Examples of these types of due-date assignment rules are 119 TWK: d i = r- + kp,. SLK: d 1 = r { + p. + k where k is some constant. It is easy to see that if all jobs are available simultaneously our assumption on the agreeability of process times and due dates covers both these cases. However, before considering the problem with agreeable process times and due dates, we have the following result for the special case where all jobs have equal processing times. Recall that we index the jobs in order of ascending due dates. Proposition 6.1: The l/p^p^/Tmax problem is optimally solved by the following algorithm: Successively group the B jobs with smallest indices into batches. Note that the batch containing the jobs with highest indices may be partially empty. Proof: By Lemma 6.2 we know that in an optimal solution the jobs must be in batch-EDD order. Because processing times are equal for all jobs, it is easy to see that all batches should be full except possibly the last batch to be processed. Q.E.D. As was the case for the 1/r. ,p,-=p, B/Tmax problem with agreeable release times and due dates, we can show that the 120 optimal solution to 1/B/Tmax with agreeable process times and due dates will possess the property that jobs will be in batch-EDD order. Lemma 6.4: In the 1/B/Tmax problem with p. < p- implying d- < dj, if a feasible solution exists there exists a feasible solution with the jobs in batch-EDD order. Proof: Similar to that of Lemma 6.2. Q.E.D. We can now present a dynamic programming algorithm similar to Algorithm DP2 to determine whether or not a feasible solution exists. Algorithm DP3: Let f(j) denote the minimum completion time of jobs l,...,j if they can be feasibly scheduled, and infinity otherwise. Then f(0) ■ 0, f(j) = oo for j < 0. f(j) = min{f J (j) Ij-B+I < i < j} where f(i-l)+ Pj , if f(i-l)+ Pj < d, f,(j) - < oo, otherwise denotes the completion time of jobs 1 through j when jobs i,i+i,...,j are processed in the last batch. 121 The justification of this algorithm is similar to that of Algorithm DP2 . Algorithm DP3 can now be integrated into a procedure similar to Algorithm TMAX1 to minimize Tmax. The only- difference from Algorithm TMAX1 is that instead of Algorithm DP2, Algorithm DP3 is used in Step 1 to determine whether or not a feasible schedule exists. This procedure we shall refer to as Algorithm TMAX 2 . As was the case for Algorithm DP2 , the complexity of Algorithm DP3 is O(nB) . An upper bound on Tmax is provided b Y n P maX ' where p max = max, {p,}. Thus the time complexity of Algorithm TMAX2 is 0[nBlog 2 (np max ) ] . Minimizing Number of Tardy Jobs In this section we examine the problem of minimizing the number of tardy jobs. The general problem with release times, l/rj,B/SU,, is NP-hard even for B=l [59,60], although the case with agreeable release times and due dates has been solved by Kise et al.[58]. We would conjecture that the problem where all jobs are available simultaneously, 1/B/SU,, is also NP-hard. We provide a polynomial-time dynamic programming algorithm for the l/r=,p } =p,B/EU, problem with agreeable release times and due dates and the 1/B/SU- problem with agreeable process times and due dates. 122 Let us first consider the l/r^p^p^B/EU, problem with agreeable release times and due dates. For the rest of this section we shall assume that all jobs are indexed in order of ascending due dates . We have the following result: Lemma 6.5: In the l/r^p^p^/ZU,- problem with agreeable release times and due dates, there exists an optimal solution which has the form (A,T) where A is a set of batches containing the jobs completed on time and T is the set of tardy jobs in any feasible sequence. Also the jobs completed on time will be in batch-EDD order. Proof: Let S be an optimal schedule, A the set of jobs completed on-time and T the set of tardy jobs. Rearranging S so that the jobs in T are completed after all jobs in A while maintaining the relative order and batching of the jobs in A cannot increase the completion time of any job in A. Since all jobs in A are on time, Tmax=0 for the set of jobs in A. Hence by Lemma 6.2, there exists a sequence for A such that all jobs in A are on time and in batch-EDD order. Q.E.D. Lemma 6.6: In the l/r J -,p,-=p / B/SU 1 . problem with agreeable release times and due dates, there exists an optimal solution where the batches that finish on-time, i.e., contain no tardy jobs, contain only consecutive jobs. In 123 other words, if a batch B which completes on time contains k<B jobs, and i is the smallest indexed job in B, then B contains the jobs i, i+l, . . . , i+k-1. Proof: Since the set of on-time jobs can be arranged in batch-EDD order by Lemma 6.5, we only need to show that in any non-tardy batch B it is impossible that B contains i and i+2 and not i+l. If such a situation were to occur, i+l must be a tardy job since if it were non-tardy it would violate the batch-EDD ordering. By the assumption of agreeable release times and due dates, r j+1 < r j+2 , which implies job i+l is available when batch B starts processing and that d j+1 < d 1+2 . Then we can replace job i+2 in batch B with job i+l. Since i+2 is on time and d i+1 < d j+2 , i+l will be on time, i+2 will now be tardy and we have no extra tardy jobs. Q.E.D. Based on this property we can develop a dynamic programming procedure for this problem. Algorithm DP4: Let f(i,j) denote the minimum finishing time of the on- time batches in a partial sequence considering jobs l,...,j where i jobs are completed on time. Then f(0,i)=0 for 1 < i < n, f(i,j) = °o for all i,j > 0. f(i,j) = min { min {f k (i,j)| l<k<B } , f(i,j-l) } 124 where max{f (i-k, j-k) ,rj}+p, if max{f (i-k,j-k) f rj}+p} <dj. k+1 f k (ifj) - oo, otherwise f k (i,j) denotes the finishing time of the on-time jobs in a partial sequence considering jobs l,...,j when i jobs are on time and k jobs are processed in the last batch. The optimal number of tardy jobs will be max (i|f(i,n) < oo, 1 < i < n} . This is due to the fact that the last non-tardy batch must contain consecutive jobs by Lemma 6.6. The number of states in this dynamic program is n 2 , and each state is evaluated in 0(B) operations. Hence the complexity of DP4 is 0(n 2 B) . The extension of DP4 to the 1/B/SU,. problem with p. < Pj implying d- < dj is straightforward. It is easy to see that Lemmas 6.5 and 6.6 hold for this problem as well. Thus in order to extend DP4 to this problem, we only need to redefine f k (i,j) as follows: f(i-k,j-k)+ Pj , if f(i-k,j-k)+ Pj < dj.. k+1 f k (i,j) = < oo, otherwise Hence we see that it is possible to solve this problem as well in 0(n 2 B) time. 125 Parallel Batch Machines In this section we shall examine various parallel batch machine scheduling problems. Throughout this section we shall assume that we are given m parallel identical batch processing machines. Other notation and definitions will remain the same as for the single machine problems. We will first consider the problem of minimizing total flowtime on parallel batch machines, P/B/EF,. . For B=l the problem is solvable in polynomial time using the Shortest Processing Time (SPT) algorithm[3] . Assume that jobs are indexed in order of non-decreasing processing times. We can prove the following: Proposition 6.2: In an optimal solution to the P/B/SF,- problem, batches on the same machine will be in batch-SPT order. Proof: Similar to the proof of Lemma 6.1 for the single- machine case. Q.E.D. Given this property, we can develop a dynamic programming algorithm to solve P/B/SF,- as follows: Algorithm DP5: Let f(j) denote the minimum total flow time in a partial schedule containing jobs l,...,j. Let F(i,j), 126 i=l,...,m denote the completion time of the jobs scheduled on machine i in the sequence corresponding to f(j). f(0)=0, F(i,0) = for i=l,...,m f(j) = °°/ F(i,j) =°° for all j<0, l<i<m f(j) = min { f(j-k) + k min { F(i,j-k)+p. }} Kk<B Ki<m F(i,j) = < F(i,j-q)+Pj, if f(j) = f(j-q) + q {F(i, j-q)+Pj} for some q F(i,j-1) , otherwise. The optimal value is given by f (n) . There are n states in this dynamic program, and each state is evaluated in O(mB) steps. Thus the complexity of this procedure is O(nmB) . We now consider the problem of minimizing makespan on parallel batch machines, P/B/Cmax. This problem is NP-hard in the strong sense even for B=l [59,60], but considerable research has been devoted to analyzing approximation algorithms. One of the most successful in practice is the LPT algorithm, which has been shown to have a worst-case error bound of 4/3 [48]. We have the following result: Proposition 6.3: Suppose we reindex the jobs in descending order of processing times. Then there exists an optimal solution to the P/B/Cmax problem such that all batches will contain consecutive jobs. Also all batches except possibly the one containing the highest indexed job will be full. 127 Proof: Consider two batches P and Q, perhaps on different machines. Suppose there are two jobs i and j such that p. < Pj and ieP, jeQ, and there exists a job keP such that p k > Pj. Suppose we move i to Q and j to P. Since p k > p., the completion time of P is not worsened, while since p. < p. the completion time of Q is not worsened. Repeating this process, we see that all batches in an optimal solution will contain consecutive jobs. Note that all batches except possibly one must be full since if a batch is partially- full, its completion time is not worsened by filling it with jobs having smaller processing times than the largest job in the batch. This implies that only the batch containing the job with the smallest processing time or largest index can be partially empty. Q.E.D. Due to the fact that the processing time of a batch is equal to the processing time of the job in the batch having the longest processing time, it is possible to view all the jobs in the same batch as a single aggregate job, with process time equal to the processing time of the batch, i.e., the longest job. The proposition above allows us to determine the batch structure of an optimal solution a priori . Thus the P/B/Cmax problem can be viewed as an equivalent unit-capacity machine P//Cmax problem. We can use the LPT heuristic developed for P//Cmax to obtain solutions to P/B/Cmax. We can state the algorithm as follows: 128 Algorithm ELPT: 1) Rank jobs in decreasing order of processing times. Batch the jobs by successively placing the B jobs with longest processing times into the same batch. Let p(B k ) be the processing time of batch B k . 2) Order the batches in non-increasing order of p(B k ) and assign them to the machines as they become free. Note that the first step of the algorithm batches the jobs according to the result of Proposition 6.3, and that the second step applies the LPT heuristic to the P//Cmax problem obtained by aggregating the jobs in the batches. We have the following result: Proposition 6.4: Let C* denote the optimal solution to the P/B/Cmax problem, and C(ELPT) the makespan value obtained by Algorithm ELPT. Then C(ELPT) < (4/3 - l/3m)C*. Proof: We know from Proposition 6.3 that an optimal solution to P/B/Cmax must have the batch structure constructed by the algorithm. Given the batch structure, it can be seen that P/B/Cmax is eguivalent to the P//Cmax problem obtained by considering batches as jobs with processing times egual to that of the longest job in the batch, and that the two problems will have the same optimal makespan C*. In the second step of the algorithm we are applying the LPT 129 heuristic to the P//Cmax problem, and we know that for this problem this heuristic will yield a makespan C(LPT) < (4/3 - l/3m)C*. Q.E.D. Summary In this chapter the area of scheduling batch processing machines has been extensively explored. The motivation for this work was the need to develop procedures for solving subproblems related to burn-in operations. In terms of complexity classification the results can be summarized as follows. With the exception of the first problem, others have been classifies for the first time by this research. Problem Classification 1/B/Cmax P 1/B/EF, P 1/B/Tmax Open 1/B/Tmax, agr.p i ,d, P VPi = Pf B/Tmax P 1/rj , B/Tmax NP-Hard i/rj f p,«p f B/Tmax Open l/r j, p,-=p, B/Tmax agr. r-, d. P l/r^B/SU,. NP-hard l/r^p^p^/SU. Open Reference Bartholdi Section 1 Section 2 Section 2 Section 2 130 Problem l/r^p.^B/SU, agr. r,., d, 1/B/SU, 1/B/ZU. agr.p f ,d f P/B/SPj P/B/Cmax Classification P Open P P NP-hard Reference Section 3 Section 3 Section 4 Of the open problems, we would conjecture that 1/B/Tmax and 1/B/SU,- are NP-hard. We have also shown that certain results pertaining to the worst-case performance of heuristics developed for parallel identical machines can be extended to the case of parallel batch processing machines. CHAPTER VII PROTOTYPE IMPLEMENTATION OF APPROXIMATION METHODOLOGY Introduction In Chapter IV the problem of scheduling a semiconductor test facility was formulated as a job shop scheduling problem and an approximation methodology for its solution outlined. This methodology proceeds by dividing the job shop into a number of workcenters and scheduling these individually, using a disjunctive graph to capture interactions between the workcenters. The implementation of such a methodology in any real world environment requires efficient methods of obtaining good schedules for the individual workcenters. In Chapters V and VI various solution procedures for workcenters consisting of a single machine with sequence-dependent setup times and single and multiple batch processing machines were developed and analyzed. In this chapter we illustrate the integration of one of the algorithms analyzed in Chapter V into a prototype implementation of the approximation methodology. In order to do this we first describe the hypothetical environment in which the methodology is to be implemented, and then present 131 132 the details of the prototype implementation of the approximation methodology. In a final section we present the results of preliminary computational experimentation with the approximation methodology. Since it is prohibitively time-consuming to obtain optimal solutions for any but the smallest problems, we compare the performance of the approximation methodology with a dispatching rule similar to those currently in use in industry. We show that the approximation methodology obtains solutions of comparable quality to those obtained by the dispatching rule, and discuss ways to further improve its performance. Implementation Environment For a prototype implementation of the methodology we consider a subset of a testing facility consisting of a number of testing workcenters and a brand workcenter. This configuration is very similar to the digital test facility of a large semiconductor manufacturer extensively studied by the author. While in the real facility there may be more than one machine of a given type, we shall assume that all such groups of machines can be approximately modelled as single machine workcenters. The test workcenters, as described in Chapter III, have sequence-dependent setup times while the brand workcenter does not. Product flows from the testers to the brand workcenter and then out of the facility. Each product is tested on a specific tester. Thus 133 there is no flow of work between the different test workcenters. The product flows are assumed to be similar for all products and to consist of the operations described below: 1) Initial room temperature testing 2) Low temperature testing 3) High temperature testing 4) Branding We shall adopt maximum lateness (Lmax) as the performance measure to be minimized in this environment. An example of such an environment consisting of four test workcenters and a brand workcenter is shown in Figure 7.1. Implementation of Approximation Methodology From the point of view of implementing the approximation methodology, we first note that there are two different types of workcenter: i) The test workcenters, consisting of a single machine with seguence-dependent setup times. The multiple operations on each lot are represented by precedence constraints. This scheduling problem, 1/rj ,prec, SDST/Lmax, is NP-hard (see Chapter V) . ii) The brand workcenter, where there are no precedence constraints or setup times. The problem of scheduling this workcenter, 1/rj/Lmax, is again NP-hard [ 59 , 60] . 134 TJ 0) w -C -o CO o c o o fc. %m l_ 1_ CD CD CD CD ■*-* ■♦-- •*-» w CO CO CO .^ CD CD CD 1- H h- H -1-1 u fa M a •H ■ui H a, S 3 M •H fa 1 * C Q_ 135 The critical components of the approximation methodology are the algorithms used to determine the critical workcenter and to sequence it. We would want these algorithms to be fast from a computational standpoint and to yield good solutions, preferably optimal ones. However, since it is difficult to obtain optimal schedules for the testing workcenters for any but the smallest problems, we use the Extended Jackson Rule for both determining criticality and for sequencing the critical workcenter. The motivation behind this decision is the following: - Analytically proven worst-case bounds for this algorithm, both in the presence and absence of sequence- dependent setup times. When applied to the equivalent problem of minimizing makespan in the presence of release times and delivery times, the worst-case performance of this algorithm in the absence of sequence-dependent setup times has been shown by Carlier[20] to differ from the optimal value by at most the value of one of the processing times. In Chapter V it has been shown that the algorithm will yield a worst-case solution of twice the optimal value of the problem without sequence-dependent setups if release times and due dates are agreeable. For arbitrary release times and due dates the worst-case performance was shown to be three times the optimal value of the problem without setups. - Applicability of the algorithm to both the testing and branding workcenters 136 - Low computational burden ( O(nlogn), where n is the number of operations to be sequenced) . Another important component of the methodology is the algorithm used to solve the longest path problems required to capture the interactions of the workcenters from the disjunctive graph representation and the incorporation of this information into the subproblems. In this implementation an 0(n 2 ) labelling algorithm was used to avoid having to renumber the nodes in a topological order. This algorithm constitutes by far the greatest part of the computational burden. Use of the 0(n) procedure developed by Adams et al.[l] would result in substantial savings. It should be noted that the methodology is not guaranteed to yield a feasible solution, i.e. , an acyclic graph, at each iteration. The reason for this is that fixing the disjunctive arcs associated with a particular workcenter in an acyclic manner does not guarantee that the directed graph for the whole facility is acyclic. In order to handle this problem, each time a machine was scheduled the resulting directed graph for the entire facility was checked for cycles. If a cycle had occurred, the machine responsible was identified and rescheduled. This was done by finding which operation was being completed before its predecessor, updating the release time of that operation to that machine with the completion time of the predecessor and reapplying the Extended Jackson Rule to that machine. In all but one of 137 the sample problems solved, this procedure resulted in infeasibilities being resolved. However, since a number of the local problems may need to be resolved, this leads to a certain increase in computational burden. A more efficient approach to dealing with this problem will form part of future research. We can now summarize the prototype approximation methodology as follows: Step l; Represent the facility using a disjunctive graph as described in Chapter IV. Obtain an initial set of release times and due dates for each workcenter by solving longest path problems in the graph corresponding to the situation where no machine has had its schedule fixed. Step 2 : Seguence each workcenter whose schedule has not yet been fixed using the Extended Jackson Rule. Select the workcenter with largest Lmax value as the most critical. Fix the schedule of this workcenter and check for cycles. If a cycle is found, reschedule the relevant workcenter to restore feasibility. Step 3 : For each workcenter already scheduled, perform the following steps: - Update the release time and due date information using the longest path procedure as described in Chapter IV, - Resequence the workcenter using the new information thus obtained, again using the Extended Jackson Rule, 138 - Check for cycles in the resulting graph and reschedule to eliminate those found. In this implementation, Step 3 was performed twice for all unscheduled workcenters at that iteration. Step 4 : If all workcenters have been scheduled, stop. Else, go to Step 2. We shall now present the results of a preliminary computational study of this implementation using data derived from a real test environment. Computational Testing The methodology outlined above was run on 24 test problems and compared with an Earliest Due Date dispatching rule. The dispatching rule gives priority to the available operation whose predecessors have already been completed that belongs to the lot having the earliest due date. During this experiment it was assumed that all test workcenters had equal workload and that all lots to be scheduled were available simultaneously. Information on process and setup times was derived from data gathered in the actual facility motivating this research. This information is summarized below: Process Times Initial room temp, test 6 seconds/chip Low temp, test 8 seconds/ chip 139 High temp, test 8 seconds/chip Brand 0.5 seconds/ chip Setup Times Sequence-dependent setup times occur only for the testing workcenters. For operations i and j carried out on the same tester, the setup time required to change from i to j , s r} , was assumed to be uniformly distributed over the interval [0,p.], where p. } is the processing time of the operation being set up. This assumption is based on observation of the production equipment in use, and was also used in the worst-case analysis of the Extended Jackson Rule in Chapter V. Lot Sizes Exponentially distributed with a mean of 800 chips per lot. Due Dates Uniformly distributed between -960 minutes and 5760 minutes. This is based on the assumption of a 480 minute shift, and allows for lots to be already late when they arrive at the testing facility. The upper limit corresponds to four three- shift days, and is derived from current practice. Experimental Results We examined two facilities, one consisting of two test systems and a brand workcenter and the other of four test systems and a brand workcenter. Each configuration was examined with different numbers of lots per tester. For each 140 combination of facility configuration and number of lots per tester, five randomly generated problems were solved using the approximation methodology and the dispatching rule. Of these, one problem was discarded due to the approximation methodology yielding an infeasible solution, and another due to biased input data (small lot sizes resulting in processing times of zero for one lot) . The results are summarized in Table 7.1. The dispatching rule value was used as a baseline for comparison. Hence the percentage deviation of the maximum lateness obtained by the approximation methodology from the value obtained by the dispatching rule is given. This value is calculated as Lmax (approximation methodology) - Lmax (dispatching rule) Lmax (dispatching rule) The results shown in Table 7.1 indicate that the approximation methodology provides the same quality of solution on average as the dispatching rules. This is encouraging, since in their study, Adams et al.[l] found that their approximation approach yielded improvements of 10% at most over dispatching rules for makespan. Hence our findings are on the same order as theirs, especially when the more complex performance measure we are trying to minimize is considered. The results are even more encouraging when we note that the implementation described in this chapter does not solve the local problems to optimal ity, as did Adams et al.[l]. Table 7.1 Computational Results 141 Lmax (mins) Machines Lots/Tester Approximation Disp, Methodology Rule %Deviation 2 4 776 776 1271 1189 6.8 1509 1517 -0.5 634 634 1976 1810 9.2 2 5 834 834 -79 -79 1316 1316 1001 1001 4 2 768 768 1532 1532 1081 1081 991 991 4 4 3345 3571 -6.3 718 287 150.2 1030 1030 1299 1299 1354 1409 -3.9 4 5 2757 2757 1320 1700 -22.4 2288 1670 37.0 1496 3234 -53.7 1696 1288 31.0 142 It should be noted that the algorithm used to schedule the workcenters is a heuristic, not an optimal procedure. Furthermore, it does not take the sequence-dependent setup times into consideration. The use of a heuristic that takes setup times into account should improve the results greatly. This could be done by applying the neighborhood search procedure described in Chapter V to the schedule obtained by the Extended Jackson Rule for the critical machine at each iteration. Another point is that the Extended Jackson Rule uses the due dates and release times estimated using the longest path procedure and the disjunctive graph. The accuracy of these estimates is of extreme importance to the effectiveness of the overall methodology. As was discussed in Chapter IV, the longest path procedure will tend to underestimate lead times since it ignores machine interference effects at machines not yet scheduled. The multi-terminal structure of the graph representation used, compared to the single sink structure used when minimizing makespan, further complicates this problem. Better techniques for estimating release times and due dates for the local problems should lead to enhanced performance of the approximation methodology. From a computation time perspective, the dispatching rules are unquestionably much faster. The use of an 0(n) procedure for the longest path problems solved at each step 143 of the approximation methodology would greatly reduce the difference in computational effort. The more efficient coding of the algorithms involved would also help alleviate the differences. Summary and Conclusions In this chapter we have demonstrated the implementation of the overall approximation methodology in a realistic scenario and compared its performance with a dispatching rule similar to those currently used in industry. The approximation methodology has been shown to yield comparable solutions, and directions to further improve the quality for the solutions obtained and the computational efficiency have been outlined. The results of this chapter demonstrate that approximation methodologies of this type have the potential for application in real-world environments and that, with the development of more efficient algorithms for the various workcenter problems and due-date estimation issues, should provide schedules superior to those obtained from dispatching rules. The results of this study and those of Adams et al.[l] indicate that improvements of the order of 5-10% on average over dispatching rules can be expected. The benefits resulting from improved schedules must be weighed against the extra computational effort required by the methodology. However, especially in heavily loaded 144 facilities, improvements of the order of 5% in performance measures like maximum lateness or number of tardy jobs could lead to substantial improvements in customer service which would justify the extra computational effort. Especially when implemented on a rolling horizon basis in a dynamic environment, where new schedules are generated say once a shift instead of in real time, these methods offer an alternative to dispatching rules for scheduling complex facilities. CHAPTER VIII SUMMARY AND FUTURE DIRECTIONS Summary of Accomplishments The purpose of this research has been to develop production scheduling methodologies for a class of job shop problems whose structure is derived from semiconductor test operations. Chapter II outlined the general semiconductor manufacturing process, and described the testing process which provides the motivation for the problems examined in this study. Chapter III presented a review of the relevant literature in the areas of scheduling theory and semiconductor manufacturing. Based on this review, the contributions of this research to the areas of scheduling theory and operations management in the semiconductor industry were assessed. In Chapter IV the general problem solving scheme by which the problem of scheduling the job shop under study will be solved was outlined. This is an approximation method similar to the Shifting Bottleneck approach of Adams et al.[l], which iteratively solves a set of subproblems in which individual workcenters are scheduled. This approach is extended in a number of ways in this chapter to allow for 145 146 lateness-related performance measures, sequence-dependent setup times and different types of workcenters. A number of important issues in the development of such a methodology were also discussed in this chapter. Chapter V presented detailed formulations and complexity classifications for a class of scheduling problems arising from the need to schedule workcenters consisting of a single machine. These problems are all NP- hard and are characterized by sequence-dependent setup times, precedence constraints and lateness-related performance measures. Optimal implicit enumeration algorithms were provided for the cases where all jobs are available simultaneously. Heuristics were developed and analyzed for a number of other cases and tight error bounds were derived for thSse heuristics under extremely mild assumptions on the relation between setup and processing times. The work in this chapter constitutes the first analysis of heuristic algorithms for scheduling problems with lateness-related performance measures and sequence- dependent setup times to date in the literature. In Chapter VI another class of scheduling problems little examined to date, those of scheduling batch processing machines, is examined. These problems are motivated by the need to schedule burn-in operations in the semiconductor test environment. Polynomial-time solution procedures are presented for a number of problems involving 147 single and parallel identical batch processing machines. A heuristic developed for the case of parallel identical machines is extended to parallel batch processing machines and a comprehensive complexity classification of these problems is given. Chapter VII provides a sample implementation of the overall approximation methodology using some of the results and algorithms developed in the previous chapters in a scenario based as closely as possible on a real testing facility. The results of the methodology are compared with the results obtained by the current practice, and the viability of the approach demonstrated. In the rest of this chapter we shall examine how the work in this dissertation can be extended. These future directions will be discussed under three main headings: single and parallel machine problems, batch scheduling problems and the extension of the approximation methodology. Single and Parallel Machines As was described in Chapter V, the majority of the single-machine problems of interest in this research are NP- hard even when all jobs are available simultaneously. We have developed implicit enumeration algorithms for the problems of minimizing Lmax and XXJ. when all lots are available simultaneously. We also develop heuristics with 148 tight worst-case error bounds for the problem of minimizing Lmax with dynamic job arrivals. Results to date indicate that it is difficult to develop efficient branch and bound algorithms for these problems. The reason for this is that it is difficult to obtain tight lower bounds. Experimentation with Algorithm BB developed in Chapter V for the l/prec,SDST/Lmax problem indicates that bounds increase very slowly as enumeration proceeds and that the lower bounds are in general weak. Another factor is that the subproblems that must be solved to yield lower bounds are often themselves NP-hard. The presence of non-simultaneous release times makes these difficulties even more acute. An interesting direction to explore in future work is the application of integer programming techniques developed in recent years for the TSP. These methods make use of facet cuts in order to generate sharp lower bounds which can be used in branch and bound algorithms. For example, formulating the l/prec,SDST/Lmax problem as a TSP with time window constraints and different objective functions would allow some of the new integer programming technology to be brought to bear on this problem. The successful extension of heuristics developed for problems of minimizing Lmax without sequence-dependent setup times is not likely to carry over to the problems of minimizing ELK . This performance measure is in general more 149 difficult to optimize than Lmax, and the presence of sequence-dependent setup times renders invalid a great majority of the results used to develop good lower bounds for the cases without sequence-dependent setups. A natural extension of this work is to examine measures of performance related to tardiness. While the l//ST i problem is NP-hard even without sequence-dependent setups [59 , 60] , enumeration algorithms and heuristics may be developed and analyzed, as well as incorporated into the overall approximation methodology. The problems of minimizing Lmax and SU^ on parallel identical machines are both NP-hard in the strong sense even without precedence constraints or sequence-dependent setups [59, 60] . Thus, the problems of interest with precedence constraints and sequence-dependent setup times, P/prec,SDST/Lmax and P/prec, SDST/SU,. , are both NP-hard in the strong sense. However, Gusfield[50] has developed worst- case error bounds for the P/r./Lmax problem. The extension of these algorithms to the case with sequence-dependent setups may be possible under certain assumptions on the nature of the setup times. Batch Processing Machines In Chapter VI we presented polynomial-time solution procedures for a number of problems dealing with the scheduling of single and parallel batch processing machines. 150 The results of this work are summarized in the table at the end of that chapter. A direction for future research is the examination of the open problems, 1/B/SU,. and 1/B/Tmax, to either provide rigorous proof of their NP-hardness or a polynomial-time solution procedure. Further work can be done on the development and analysis of heuristics for the problems known to be NP-complete, such as was done for the P/B/Cmax problem. The problems of minimizing Lmax and SUj on parallel batch machines are NP-hard even for a batch size of one [59, 60], but polynomial and/or pseudopolynomial solution procedures may be obtainable under certain assumptions on the processing times and due dates. The problem of minimizing total tardiness on a single batch processing machine, l/B/ETj , is also in the same situation. The work on batch processing machines can also be extended by generalizing the model of batch processing machines used in this dissertation. A critical assumption in the work to date is that all jobs reguire exactly the same amount of oven capacity, i.e., are of the same size. In reality, however, the amount of oven capacity a job may require depends on the size of the lot of chips represented by that job. Another interesting direction for future work is the consideration of multi-stage systems containing batch processing machines. Ahmadi et al.[2] have examined a number of problems in this area with the goal of minimizing 151 flowtime-related performance measures. However, the batch machine model they use is somewhat simpler than the one used in this dissertation. While a great many of the scheduling problems that will arise in these systems are likely to be NP-hard, it may be possible to develop polynomial-time algorithms for special cases and to develop and analyze good heuristics. Overall Approximation Scheme In Chapter IV the problem of scheduling a semiconductor test facility was formulated as a job shop scheduling problem and the overall approximation scheme to be used in its solution presented. The approximation methodology is similar to the Shifting Bottleneck procedure of Adams et al.[l], but is extended in a number of directions. A sample implementation of the approximation scheme was illustrated in Chapter VII. The first step in any future research in this area is to work out the implementation details for the methodology when a number of different types of workcenter are present. Specifically, modification of the disjunctive graph used to represent the state of the job shop to enable representation of parallel identical machines and single and parallel batch processing machines need to be examined. Bartholdi et al.[15] have examined a number of these issues but further research is needed. Another area of interest for future work 152 is the due date estimation mechanism. The current mechanism, based on the longest path calculations as the schedule is constructed, ignores machine interference effects at the machines not yet scheduled. Vepsalainen and Morton [95] have shown that including an estimate of waiting times at machines not yet visited into the due date estimation improves performance considerably. The methodology in its present state addresses a static problem, where it is assumed that all lots to be processed over a planning horizon are available at time zero. However, in most real-world manufacturing environments, the arrival of jobs to a production facility is dynamic. This is certainly true in the semiconductor industry, where lots are constantly arriving at the test area from a number of different sources. Hence the extension of the methodology developed in this dissertation to handle the case of the dynamic job shop would be a valuable contribution. An important characteristic of the semiconductor testing process is that since processing times are long, job arrivals do not occur at very frequent intervals. Interarrival times of lots at testing workcenters have been found to be of the order of hours rather than minutes or seconds. Thus the eight-hour shift constitutes a valid time frame for scheduling purposes. Given this insight, and the fact that jobs arrive over the course of a shift, we can implement the approximation methodology on a rolling horizon 153 basis. The main idea is that at the beginning of each shift the current state of the shop, i.e., available jobs and times when machines will complete processing the job currently being worked on and become available, will be viewed as a static problem. This static problem will be solved using the methodology and the solution implemented for that shift. At the start of the next shift, the system status will be updates and the procedure repeated. Rolling planning horizon approaches have been extensively examined in the context of production planning and dynamic lot sizing problems (see Lee and Denardo[69] for an example) . Raman et al.[87] give an example of such an implementation in the scheduling of a general flexible manufacturing system. The extension of the methodology to a rolling horizon implementation poses some interesting problems. Due to the fact that preemption is not possible in the testing operation, jobs occupying machines at the beginning of each shift must be completed before new work can be assigned to that machine. This leads to non-simultaneous ready times for machines as well as jobs. Extension of the methodology to handle this feature would require the development of solution procedures that were capable of handling non- simultaneous machine and job availability. The work of Lee [70] examining parallel identical machine scheduling with simultaneous job availability but non-simultaneous machine 154 availability seems to be the only related research in the literature. Finally, the point should be made that the methodology as developed in Chapter IV is an extremely flexible one. Given a particular facility, an engineer can design his own implementation by putting together the various algorithms for the subproblems representing the various workcenters to be scheduled. The prototype implementation described in Chapter VII is an example. The level of detail in the representation of the facility, e.g., should a group of three identical test systems be treated as one workcenter or as three, is up to the user, although data reguirements should be taken into account. Given the large mainframe computers used to run commercial CIM systems such as COMETS described in Chapter III, the methodology should be capable of being used effectively in fairly sizeable facilities. REFERENCES [1] Adams, J., Balas,E. and Zawack, D. , "The Shifting Bottleneck Procedure for Job-Shop Scheduling," Management Science Vol.34, No. 3, 391-401, 1988. [2] Ahmadi , J . H . , Ahmadi,R.H. , Dasu,S. and Tang,C.S., Batching and Scheduling Jobs on Batch and Discrete Processors , Anderson School of Management, University of California, Los Angeles, 1989. [3] Baker, K.R. . Introduction to Sequencing and Scheduling , Wiley, New York, 1974. [4] Baker, K.R. , "Sequencing Rules and Due Date Assignments in a Job Shop," Management Science Vol.30, No. 9, 1093-1104, 1984. [5] Baker, K. R. , "An Elimination Method for the Flow-Shop Problem," Operations Research Vol.23, No.l, 159- 162, 1975. [6] Baker, K.R. , "A Comparative Study of Flowshop Algorithms," Operations Research Vol.23, No.l, 62- 73, 1975. [7] Baker, K.R. and Su, Z.S. , "Sequencing with Due Dates and Early Start Times to Minimize Maximum Tardiness," Naval Research Logistics Quarterly , Vol.21, 171- 176, 1974. [8] Balas,E. , "Machine Sequencing via Disjunctive Graphs: An Implicit Enumeration Approach," Operations Research Vol.17, 941-957, 1969. [9] Balas,E., "Project Scheduling with Resource Constraints," in Applications of Mathematical Programming Techniques , E.M.L. Beale (ed.), The English Universities Press Ltd, London, 1970 [10] Balas,E. , "Machine Sequencing: Disjunctive Graphs and Degree-Constrained Subgraphs," Naval Research Logistics Quarterly Vol.17, No. 1, 1970. 155 156 [11] Balas,E.," On the Facial Structure of Scheduling Polyhedra," Mathematical Programming Study Vol.24 179-218, 1985. [12] Balas,E. and Toth, P. , "Branch and Bound Methods" in The Travelling Salesman Problem , E.L. Lawler, A. E.G. Rinnooy Kan, J.K. Lenstra, D.B. Shmoys(eds), John Wiley, New York, 1985. [13] Barker, J. R. and McMahon,G. B. , "Scheduling the General Job Shop," Management Science Vol.31, No. 5, 594- 598, 1985. [14] Barnes, J. W, and Vanston, L.K. , "Scheduling Jobs with Linear Delay Penalties and Sequence-Dependent Setup Costs," Operations Research Vol.29, No. 1, 146-160, 1981. [15] Bartholdi, J. J. , Lofgren,C. and Sigismondi,G. , Scheduling Technology for Semiconductor Fabrication, Tech Report NSF SBIR Grant, 1988. [16] Bitran,G.R. and Tirupati, D. , " Planning and Scheduling for Epitaxial Wafer Production," Operations Research Vol.36, No.l, 34-49, 1988. [17] Bitran,G. and Tirupati, D. , "Development and Implementation of a Scheduling System for a Wafer Fabrication Facility," Operations Research Vol.36, No. 3, 377-395, 1988. [18] Burman, D.Y., Gurrola-Gal, F. J. , Nozari,A., Sathaye,S. and Sitarik, J. P. , "Performance Analysis Techniques for IC Manufacturing Lines," AT&T Bell Labs Technical Journal Vol.65, 46-56, 1986. [19] Buxey,G. , "Production Scheduling: Practice and Theory," European Journal of Operational Research Vol. 39, No.l, 17-31, 1989. [20] Carlier, J. , "The One-Machine Scheduling Problem," European Journal of Operational Research Vol.11, 42-47, 1982. [21] Carlier, J. and Pinson, E. , "An Algorithm for Solving the Job-Shop Problem," Management Science Vol.35, No. 2, 164-176, 1989. [22] Charlton, J. M. and Death, C. C. , "A Generalized Machine- Scheduling Algorithm," Operations Research Quarterly Vol.21, No.l, 127-134, 1970. 157 [23] Charlton, J. M. and Death, C. C. , "A Method of Solution for General Machine Scheduling Problems," Operations Research Vol.18, No. 4, 689-707, 1970. [24] Chen, H. , Harrison, J. M. , Mandelbaum, A. , Van Ackere,A. and Wein,L.M., "Empirical Evaluation of a Queueing Network Model for Semiconductor Wafer Fabrication," Operations Research Vol.36, No. 2, 202-215, 1988. [25] Cheng, T.C.E. and Gupta, M.C., "Survey of Scheduling Research involving Due Date Determination Decisions," European Journal of Operational Research Vol.38, 156-166, 1989. [26] Coffman,E.G. (ed. ) , Computer and Job Shop Scheduling Theory , Wiley, New York, 1976. [27] Consilium Inc. . Short-Interval Scheduling System User's Manual, Internal Publication, Mountain View, CA. [28] Conway, R.N. , Maxwell, W.L. and Miller , L.W. . Theory of Scheduling . Addison-Wesley, Reading, MA, 1967. [29] Corwin,B.D. and Esogbue, A. 0. , "Two Machine Flow Shop Scheduling Problems with Sequence Dependent Setup Times: A Dynamic Programming Approach," Naval Research Logistics Quarterly Vol.21, 515-524, 1974. [30] Dannenbring,D.G. , "Procedures for Estimating Optimal Solution Values for Large Combinatorial Problems," Management Science Vol.23, No. 12, 1273-1283, 1977. [31] Dannenbring,D.G. , "An Evaluation of Flow Shop Sequencing Heuristics," Management Science Vol.23, No. 11, 1174-1182, 1977. [32] Dayhoff,J.E. and Atherton,R.W. , "Simulation of VLSI Manufacturing Areas," VLSI Design , 84-92, December 1984 [33] Dayhoff,J.E. and Atherton,R.W. , "A Model for Wafer Fabrication Dynamics in Integrated Circuit Manufacturing," IEEE Transactions on Systems, man and Cybernetics Vol. 17 , No.l, 91-100, 1987. [34] Dayhoff,J.E. and Atherton,R.W. , "Signature Analysis of Dispatch Schemes in Wafer Fabrication," IEEE Transactions on Components. Hybrids and Manufacturing Technology Vol.9, No. 4, 518-525, 1986. 158 [35] Dayhoff ,J.E. and Atherton , R . W . , "Signature Analysis: Simulation of Inventory, Cycle Time and Throughput Tradeoffs in Wafer Fabrication," IEEE Transactions on Components, Hybrids and Manufacturing Technology Vol.9, No. 4, 498-507, 1986. [36] Deb,R.K. and Serfozo,R. F. , "Optimal Control of Batch Service Queues," Advances in Applied Probability Vol.5, 340-361, 1973. [37] Dempster, M.A.H. , Lenstra, J.K. and Rinnooy Kan, A.H.G. (Eds) , Deterministic and Stochastic Scheduling , D.Reidel, Boston, 1982. [38] Dietrich, B. L. , Scheduling on Parallel Unrelated Machines with Set-ups . Res. Rep. RC 14279, IBM T.J. Watson Research Center, Yorktown Heights, NY, 1988. [39] Driscoll,W.C. and Emmons, H. , "Scheduling Production on One Machine with Changeover Costs," AIIE Transactions Vol.9, No. 4, 388-395, 1977. [40] Florian,M. , Trepant,P. and McMahon,G. , "An Implicit Enumeration Algorithm for the Machine Sequencing Problem," Management Science Vol.17, No. 12, B782- B792, 1971. [41] French , S . , Seguencing and Scheduling: An Introduction to the Mathematics of the Job-Shop , Wiley, New York, 1982. [42] Garey,M.R. and Johnson , D . S . , Computers and Intractability . W.H. Freeman & Co. , San Francisco, 1979. [43] Geoffrion,A.M. and Graves, G.W., "Scheduling Parallel Production Lines with Changeover Costs: Practical Application of a Quadratic Assignment/LP Approach," Operations Research Vol.24, No. 4, 595- 610, 1976. [44] Glassey,C.R. and Resende,M.G. C. , "Closed-Loop Job Release Control for VLSI Circuit Manufacturing," IEEE Transactions on Semiconductor Manufacturing Vol.1, No.l, 36-46, 1988. [45] Glassey,C.R. and Resende,M.G. C. , "A Scheduling Rule for Job Release in Semiconductor Fabrication," Operations Research Letters Vol.7, No. 5, 213-217, 1988. 159 [46] Golden, B.L. and Alt, F. B. , "Interval Estimation of a Global Optimum for Large Combinatorial Problems," Naval Research Logistics Quarterly Vol.26, 69-77, 1979. [47] Golden, B.L. and Stewart, W. R. , "Empirical Analysis of Heuristics," in The Travelling Salesman Problem" , E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan, D.B. Shmoys(eds), John Wiley, New York, 1985. [48] Graham, R.L., "Bounds on Multiprocessor Timing Anomalies," SIAM Journal of Applied Mathematics Vol.17, 416-429, 1969 [49] Gupta, J.N. D. , "Flowshop Schedules with Sequence Dependent Setup Times," Journal of the Operations Research Society of Japan Vol.29, No. 3, 206-219, 1986. [50] Gusfield,D. , "Bounds for Naive Multiple Machine Scheduling with Release Times and Due Dates," Journal of Algorithms , Vol.5, 1-6, 1984. [51] Hall,L. and Shmoys, D. , Jackson' s Rule for One-machine Scheduling: Making a Good Heuristic Better , Research Report No. OR 199-89, Operations Research Center, Massachusetts Institute of Technology, Cambridge, August 1989. [52] Hariri, A.M. A. and Potts, C.N., "A Branch and Bound Algorithm to Minimize the Number of Late Jobs in a Permutation Flowshop," European Journal of Operational Research Vol.38, 228-237, 1989. [53] Heck, H. W. , Computational Schemes for Flowshops , Unpublished Ph.D Dissertation, Dept. of Industrial and Systems Engineering, University of Florida, 1973. [54] Heck,H.W. and Roberts , S . D . , Pis'] unct ive Graph Algorithms for Resource Constrained Sequencing in Flowshops: Maximum Flow Time and Maximum Tardiness , Project Themis Technical Report No. 47, Dept. of Industrial and Systems Engineering, University of Florida, Gainesville, October 1970. [55] Heck,H.W. and Roberts , S . D. , Disn unct ive Graph Algorithms for Average Flow Time and Average Tardiness , Project Themis Technical Report No. 48, Dept. of Industrial and Systems Engineering, University of Florida, Gainesville, October 1970. 160 [56] Ikura,Y. and Gimple,M. , "Efficient Scheduling Algorithms for a Single Batch Processing Machine," Operations Research Letters Vol.5, No. 2, 61-65, 1986. [57] Irani,S.A., Gunasena,U. , Davachi,A. and Enscore,E. E. , "Single-Machine Setup-Dependent Sequencing using a Complexity Ranking Scheme," Journal of Manufacturing Systems Vol.7, No.l, 11-22, 1989. [58] Kise,H., Ibaraki,T. and Mine,H., "A Solvable Case of the One-Machine Scheduling Problem with Ready and Due Times," Operations Research Vol.2 6 No.l, 121- 126, 1978 [59] Lageweg , B . J . , Lawler , E. L. , Lenstra, J.K. , and Rinnooy Kan, A.H.G. , Computer-Aided Complexity Classification of Combinatorial Problems . Report No. BW137, Mathematisch Centrum, Amsterdam, 1981. [60] Lageweg,B. J. , Lawler, E.L., Lenstra, J.K. and Rinnooy Kan , A . H . G . , Computer-Aided Complexity Classification of Deterministic Scheduling Problems, Report No. BW138, Mathematisch Centrum, Amsterdam, 1981. [61] Lageweg , B . J . , Lenstra, J.K. and Rinnooy Kan,A.H.G., "Job Shop Scheduling by Implicit Enumeration," Management Science Vol.24, No. 4, 441-450, 1977. [62] Lageweg, B. J. , Lenstra, J.K. and Rinnooy Kan,A.H.G., "A General Bounding Scheme for the Permutation Flowshop Problem," Operations Research Vol.26, No.l, 53-67, 1978. [63] Lawler, E. , "On Scheduling Problems with Deferral Costs," Management Science Vol.11, No. 2, 280-288, 1964. [64] Lawler, E. , "Optimal Sequencing of a Single Machine subject to Precedence Constraints," Management Science Vol.19, 544-546, 1973. [65] Lawler, E. L. , " Sequencing to Minimize the Weighted Number of Tardy Jobs," Revue Francaise Automatigue. Informatigue et Recherche Operationelle Vol.10, 27-33, 1976. [66] Lawler, E.L. and and Moore, J.M. , "A Functional Equation and its Application to Resource Allocation and Sequencing Problems," Management Science Vol.16, 77-84, 1969 161 [67] Leachman,R.C. , Preliminary Design and Development of a Corporate-Level Production Planning System for the Semiconductor Industry , OR Center, University of California, Berkeley, February 1986. [68] Leachman,R.C. , Solorzano,M. and Glassey r R.C. , A Queue Management Policy for the Release of Factory Work Orders , presented at ORSA/TTMS Conference, Vancouver, May 1989 [69] Lee,C.Y. and Denardo,E., "Rolling Planning Horizons: Error Bounds for the Dynamic Lot Size Model," Mathematics of Operations Research Vol.11, No. 3, 423-432, 1986. [70] Lee,C.Y., "Parallel Machine Scheduling with Non- Simultaneous Machine Available Time," to appear in Discrete Applied Mathematics f 1990. [71] Lenstra, J.K. , Seguencing by Enumerative Methods , Mathematical Centre Tract 69, Mathematisch Centrum, Amsterdam, 1977. [72] Lenstra, J.K. and Rinnooy Kan, A. H. G. , "Complexity of Scheduling under Precedence Constraints," Operations Research Vol. 28 , No.l, 22-35, 1978. [73] Lockett,A.G. and Muhlemann, A. P. , "A Scheduling Problem Involving Seguence-Dependent Changeover Times," Operations Research Vol.20, 895-902, 1972. [74] Lozinski,C. and Glassey, C.R. , "Bottleneck Starvation Indicators for Shop-Floor Control," IEEE Transactions on Semiconductor Manufacturing Vol.1, No. 4, 147-153, 1988. [75] Matsuo,H., Suh, C.J. and Sullivan, R.S . , A Controlled Search Simulated Annealing Approach for the General Jobshop Scheduling Problem , Working Paper No. 03-04-88, Dept. of Management, Graduate School of Business, University of Texas at Austin, 1988 [76] McMahon,G. and Florian,M. , "On Scheduling with Ready Times and Due Dates to Minimize Maximum Lateness," Operations Research Vol.23, No. 3, 475-482, 1975. [77] Medhi,J., "Waiting Time Distribution in a Poisson Queue with a General Bulk Service Rule," Management Science Vol.21, No. 7, 777-782, 1975. 162 [78] Monma,C. and Potts, C.N. , "On the Complexity of Scheduling with Batch Setup Times," Operations Research Vol.37 No. 5, 798-804, 1989. [79] Morton, T, Lawrence, S. and Kekre,S., "SCHED-STAR: A Price Based Shop Scheduling Module," Journal of Manufacturing and Operations Management Vol.1, 131-181, 1988. [80] Neuts,M., "A General Class of Bulk Queues with Poisson Input," Annals of Mathematical Statistics Vol.38, 759-770, 1967. [81] Panwalkar,S.S. and Iskander, W.,"A Survey of Scheduling Rules," Operations Research Vol.25, No.l, 45-61, 1977. [82] Park,Y.B., Pegden,C.D. and Enscore,E.E. , "A Survey and Evaluation of Static Flowshop Scheduling Heuristics," International Journal of Production Research Vol.22, No.l, 127-1451, 1984. [83] Parker, R.G., Deane,R.H. and Holmes, R. A. , "On The Use of a Vehicle Routing Algorithm for the Parallel Processor Problem with Seguence-Dependent Changeover Costs," AIIE Transactions June 1977, pp. 155-160, 1977. [84] Picard,J.C. and Queyranne,M. , "The Time-Dependent Travelling Salesman Problem and its Application to the Tardiness Problem in One-Machine Scheduling," Operations Research Vol.26, No.l, 86-110, 1978. [85] Potts, C. N. , "Analysis of a Heuristic for One Machine Sequencing with Release Dates and Delivery Times," Operations Research Vol.28, 1436-1441, 1980. [86] Potts, C.N. and Van Wassenhove, L.N. , "Algorithms for Scheduling a Single Machine to Minimize the Weighted Number of Late Jobs," Management Science Vol.34, 843-858, 1988 [87] Raman, N. , Talbot, F.B. and Rachamadugu,R. V. , "Due Date Based Scheduling in a General Flexible Manufacturing System," Journal of Operations Management Vol.8, No. 2, 115-132, 1989. [88] Rodammer , F . A . and White, K.P.,"A Recent Survey of Production Scheduling," IEEE Transactions on Systems, Man and Cybernetics Vol.18, No. 6, 841- 851, 1988. 163 [89] Spence, A.M., Welter, D.J. , " Capacity Planning of a Photolithography Work Cell in a Wafer Manufacturing Line," Proceedings of the IEEE Conference on Robotics and Automation , 702-708, 1987 [90] Sze,S.M., VLSI Technology , McGraw-Hill, New York, 1983. [91] Szwarc,W. , "Optimal Elimination Methods in the m x n Flow-Shop Scheduling Problem," Operations Research Vol.21, 1250-1259, 1973. [92] Uskup,E. and Smith, S. B. , "A Branch and Bound Algorithm for Two-Stage Production Seguencing Problems," Operations Research Vol.23, No.l, 118-136, 1975. [93] Van Laarhoven,P. J.M. , Aarts,E.H.L. and Lenstra, J. K. , Job Shop Scheduling by Simulated Annealing , Res. Rep OS-R8809, Centre for Mathematics and Computer Science, Amsterdam, 1988. [94] Vepsalainen,A.P. J. and Morton, T.E., "Priority Rules for Job Shops with Weighted Tardiness Costs," Management Science Vol.33, No. 8, 1035-1047, 1987 [95] Vepsalainen,A.P. J. and Morton, T. E. , "Improving Local Priority Rules with Global Lead-time Estimates: A Simulation Study," Journal of Manufacturing and Operations Management Vol.1, No.l, 102-118, 1988. [96] Villarreal,F. J. and Bulfin,R.L., "Scheduling a Single Machine to Minimize the Weighted Number of Tardy Jobs," HE Transactions Vol.15. 337-343, 1983. [97] Wein,L.M., "Scheduling Semiconductor Wafer Fabrication," IEEE Transactions on Semiconductor Manufacturing Vol . 1 . No. 3, 115-129, 1988. [98] White, C.H. and Wilson, R. C. , "Sequence-Dependent Setup Times and Job Sequencing," International Journal of Production Research Vol.15, No. 2, 191-202, 1977. [99] Wittrock,R. J. . Scheduling Parallel Machines with Setups , Research Report RC 1174 0, IBM Thomas J. Watson Research Center, Yorktown Heights, NY 10598, 1986. BIOGRAPHICAL SKETCH Reha Uzsoy was born on April 21, 1963, in London, U.K. He received a bachelor's degree in industrial engineering in June 1984, a bachelor's degree in mathematics in June 1985 and a Master of Science in industrial engineering in June 1986, all from Bogazici University in Istanbul, Turkey. He was admitted to the Department of Industrial and Systems Engineering at the University of Florida in August 1986, and has been studying toward the Ph.D degree since that date. 164 I certify that I have read this study and that in my opinion it conforms to acceptable standards of scholarly presentation and is fully adequate, in scope and quality, as a dissertation for the degree of Doctor of Philosophy. &f-- 'artih- Vega , Chairman Louis A. Associate Professor of Industrial and Systems Engineering I certify that I have read this study and that in my opinion it conforms to acceptable standards of scholarly presentation and is fully adequate, in scope and quality, as a dissertation for the degree of Doctor of Philosophy. ~~ y-e*2L J* •ce. Chung-Yee Lee, Chairman Associate Professor of Industrial and Systems Engineering I certify that I have read this study and that in my opinion it conforms to acceptable standards of scholarly presentation and is fully adequate, in scope and quality, as a dissertation for the degree of Doctor of Philosophy. Donald \Jy. Elzinga Professor of Indus^fi Systems EngineeriTig I certify that I have read this study and that in my opinion it conforms to acceptable standards of scholarly presentation and is fully adequate, in scope and quality, as a dissertation for the degree of Doctor of Philosophy. Selcuk ErengjAc Associate Professor of Decision and Information Sciences I certify that I have read this study and that in my opinion it conforms to acceptable standards of scholarly presentation and is fully adequate, in scope and quality, as a dissertation for the degree of Doctor of Philosophy. 4>w<xy- H IaoJIWa Sencer Yeralan Associate Professor of Industrial and Systems Engineering This dissertation was submitted to the Graduate Faculty of the College of Engineering and to the Graduate School and was accepted as partial fulfillment of the requirements for the degree of Doctor of Philosophy. ^-Winfred M. Phillips Dean, College of Engineering Madelyn M. Lockhart Dean, Graduate School , >-/ : ; ;